Monday, September 12th, 2016 | 4pm-5pm | Burnside 1205 |

London School of Economics

The Multicolour Ramsey Number of a Long Odd Cycle

For a graph $G$, the $k$-colour Ramsey number $R_k(G)$ is the least integer $N$ such that every $k$-colouring of the edges of the complete graph $K_N$ contains a monochromatic copy of $G$. Let $C_n$ denote the cycle on $n$ vertices. We show that for fixed $k\ge 3$ and $n$ odd and sufficiently large, $$R_k(C_n)=2^{k-1}(n-1)+1.$$ This generalises a result of Kohayakawa, Simonovits and Skokan and resolves a conjecture of Bondy and Erd\H{o}s for large $n$. We also establish a surprising correspondence between extremal $k$-colourings for this problem and perfect matchings in the hypercube $Q_k$. This allows us to in fact prove a stability-type generalization of the above. The proof is analytic in nature, the first step of which is to use the Regularity Lemma to relate this problem in Ramsey theory to one in convex optimisation. This is joint work with Matthew Jenssen (LSE).