Date
Tue, 12 Nov 2013
Time
14:30 - 15:30
Location
L2
Speaker
Simon Griffiths
Organisation
University of Oxford

The Ramsey number $R(K_s, Q_n)$ is the smallest integer $N$ such that every red-blue colouring of the edges of the complete graph $K_N$ contains either a red $n$-dimensional hypercube, or a blue clique on $s$ vertices. Note that $N=(s-1)(2^n -1)$ is not large enough, since we may colour in red $(s-1)$ disjoint cliques of cardinality $2^N -1$ and colour the remaining edges blue. In 1983, Burr and Erdos conjectured that this example was the best possible, i.e., that $R(K_s, Q_n) = (s-1)(2^n -1) + 1$ for every positive integer $s$ and sufficiently large $n$. In a recent breakthrough, Conlon, Fox, Lee and Sudakov proved the conjecture up to a multiplicative constant for each $s$. In this talk we shall sketch the proof of the conjecture and discuss some related problems.

(Based on joint work with Gonzalo Fiz Pontiveros, Robert Morris, David Saxton and Jozef Skokan)

Please contact us with feedback and comments about this page. Last updated on 04 Apr 2022 14:57.