Cycle-Complete Ramsey Numbers

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • London School of Economics and Political Science, The (LSE)
  • University of Oxford

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.

Details

Original languageEnglish
Article numberrnz119
JournalInternational Mathematics Research Notices
Early online date10 Jul 2019
Publication statusE-pub ahead of print - 10 Jul 2019

Keywords

  • Ramsey theory