Cycle-Complete Ramsey Numbers

Peter Keevash, Eoin Long, Jozef Skokan

Research output: Contribution to journalArticlepeer-review

82 Downloads (Pure)

Abstract

The Ramsey number r(C,Kn) is the smallest natural number N such that every red/blue edge colouring of a clique of order N contains a red cycle of length ℓ or a blue clique of order n⁠. In 1978, Erdős, Faudree, Rousseau, and Schelp conjectured that r(C,Kn) = (ℓ−1)(n−1)+1 for ℓ ≥ n ≥ 3 provided (ℓ, n) ≠ (3,3)⁠. 

We prove that, for some absolute constant C ≥ 1⁠, we have r(C,Kn) = (ℓ−1)(n−1)+1 provided ℓ ≥ C (log n / log log n)⁠. Up to the value of C this is tight since we also show that, for any ε > 0 and n > n0(ε)⁠, we have r(C,Kn) ≫ (ℓ−1)(n−1)+1 for all 3 ≤ ℓ ≤ (1−ε)(log n / log log n). 

This proves the conjecture of Erdős, Faudree, Rousseau, and Schelp for large ℓ, a stronger form of the conjecture due to Nikiforov, and answers (up to multiplicative constants) two further questions of Erdős, Faudree, Rousseau, and Schelp.
Original languageEnglish
Article numberrnz119
Pages (from-to)275-300
Number of pages26
JournalInternational Mathematics Research Notices
Volume2021
Issue number1
Early online date10 Jul 2019
DOIs
Publication statusE-pub ahead of print - 10 Jul 2019

Keywords

  • Ramsey theory

Fingerprint

Dive into the research topics of 'Cycle-Complete Ramsey Numbers'. Together they form a unique fingerprint.

Cite this