Cycle-complete Ramsey numbers

Abstract

The Ramsey number $r(C_{\ell },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 $\ell$ or a blue clique of order $n$. In 1978, Erdős, Faudree, Rousseau and Schelp conjectured that $r(C_{\ell },K_n)=(\ell -1)(n-1)+1$ for $\ell \ge n\ge 3$ provided $(\ell ,n)\ne (3,3)$. We prove that, for some absolute constant $C\ge 1$, we have $r(C_{\ell },K_n)=(\ell -1)(n-1)+1$ provided $\ell \ge C\frac{\log n}{\log \log n}$. Up to the value of $C$ this is tight since we also show that, for any $\epsilon >0$ and $n>n_0(\epsilon )$, we have $r(C_{\ell },K_n)\gg (\ell -1)(n-1)+1$ for all $3\le \ell \le (1-\epsilon )\frac{\log n}{\log \log n}$. This proves the conjecture of Erdős, Faudree, Rousseau and Schelp for large $\ell$, 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.

19 pages