The multicolour Ramsey number of a long odd cycle

Research output: Contribution to journalArticlepeer-review

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. Bondy and Erdös conjectured that for an odd cycle Cn on n>3 vertices, Rk(Cn)=2k−1(n−1)+1.This is known to hold when k= 2 and n>3, and when k= 3 and n is large. We show that this conjecture holds asymptotically for k≥4, proving that for n odd, Rk(Cn)=2k−1n+o(n) as n→∞. The proof uses the regularity lemma to relate this problem in Ramsey theory to one in convex optimisation, allowing analytic methods to be exploited. Our analysis leads us to a new class of lower bound constructions for this problem, which naturally arise from perfect matchings in the k-dimensional hypercube. Progress towards a resolution of the conjecture for large n is also discussed.
Original languageEnglish
Pages (from-to)377-381
Number of pages5
JournalElectronic Notes in Discrete Mathematics
Volume49
DOIs
Publication statusPublished - 12 Nov 2015

Keywords

  • Ramsey number
  • regularity lemma
  • convex optimisation
  • hypercube

Fingerprint

Dive into the research topics of 'The multicolour Ramsey number of a long odd cycle'. Together they form a unique fingerprint.

Cite this