Cycle-Complete Ramsey Numbers. (10th July 2019) - Keevash, Peter; Long, Eoin; Skokan, Jozef
Abstract: The Ramsey number r(C_, K_n) 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_, K_n) = (-1)(n-1)+1 for ≥ n≥ 3 provided (, n) ≠ (3, 3) . We prove that, for some absolute constant C1, we have r(C_, K_n) = (-1)(n-1)+1 provided ≥ Cnn . Up to the value of C this is tight since we also show that, for any ε>0 and n> n_0(ε ), we have r(C_, K_n) (-1)(n-1)+1 for all 3 ≤ ≤ (1-ε )nn . 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.