University of Cambridge > > Combinatorics Seminar > The Multicolour Ramsey Number of a Long Odd Cycle

The Multicolour Ramsey Number of a Long Odd Cycle

Add to your list(s) Download to your calendar using vCal

  • UserJozef Skokan (LSE)
  • ClockThursday 12 October 2017, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact Andrew Thomason.

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 generalisation 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.

This talk is part of the Combinatorics Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity