|Wednesday, December 12th, 2018 at 16:15|
|Königin-Luise-Str. 24 / 26, SR 006|
|Jozef Skokan (LSE)|
|The k-colour Ramsey number of odd cycles via non-linear optimisation|
Abstract: For a graph G, the k-colour Ramsey number Rk(G) is the least integer N such that every k-colouring of the edges of the complete graph KN contains a monochromatic copy of G. Let Cn denote the cycle on n vertices. We show that for fixed k > 2 and n odd and sufficiently large,
Rk(Cn) = 2k-1(n-1) + 1.
This generalises a result of Kohayakawa, Simonovits and Skokan and resolves a conjecture of Bondy and Erdős for large n. We also establish a surprising correspondence between extremal k-colourings for this problem and perfect matchings in the hypercube Qk. 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.
To subscribe to the mailing-list of the seminar, please follow this link:
To add the .ics file of the calendar to your favorite calendar reader (that supports the ICal format), please follow this link:
To add the calendar feeds to your favorite feed reader, please follow this link:
For any request, please send an e-mail to: