Exact Ramsey numbers of odd cycles via nonlinear optimisation

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

Abstract

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≥2 and n odd and sufficiently large, R k(C n)=2 k−1(n−1)+1. This resolves a conjecture of Bondy and Erdős for large n. The proof is analytic in nature, the first step of which is to use the regularity method to relate this problem in Ramsey theory to one in nonlinear optimisation. This allows us to prove a stability-type generalisation of the above and establish a correspondence between extremal k-colourings for this problem and perfect matchings in the k-dimensional hypercube Q k.

Bibliographic note

Funding Information: We would like to thank Julia B?ttcher for helpful discussions and comments. We would also like to thank the anonymous referees for a very careful reading of this paper. Publisher Copyright: © 2020 Elsevier Inc. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

Details

Original languageEnglish
Article number107444
JournalAdvances in Mathematics
Volume376
Early online date16 Oct 2020
Publication statusPublished - 6 Jan 2021

Keywords

  • Hypercube, Nonlinear optimisation, Odd cycle, Ramsey theory, Regularity method

ASJC Scopus subject areas