The Multicolour Ramsey Number of a Long Odd Cycle

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

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in discrete mathematics 2015-11, Vol.49, p.377-381
Main Author: Jenssen, Matthew
Format: Article
Language:English
Subjects:
convex optimisation
hypercube
Ramsey number
regularity lemma
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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)asn→∞. 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.
ISSN:1571-0653
1571-0653
DOI:10.1016/j.endm.2015.06.053