The Ramsey number of loose cycles versus cliques

Abstract

Recently Kostochka, Mubayi and Verstraëte initiated the study of the Ramsey numbers of uniform loose cycles versus cliques. In particular they proved that $R(C_3^r,K_n^r)=\tilde{\theta }(n^{3/2})$ for all fixed $r\ge 3$. For the case of loose cycles of length five they proved that $R(C_5^r,K_n^r)=\Omega ((n/\log n{)}^{5/4})$ and conjectured that $R(C_5^r,K_n^r)=O(n^{5/4})$ for all fixed $r\ge 3$. Our main result is that $R(C_5^3,K_n^3)=O(n^{4/3})$ and more generally for any fixed $l\ge 3$ that $R(C_l^3,K_n^3)=O(n^{1+1/\lfloor (l+1)/2\rfloor })$. We also explain why for every fixed $l\ge 5$, $r\ge 4$, $R(C_l^r,K_n^r)=O(n^{1+1/\lfloor l/2\rfloor })$ if $l$ is odd, which improves upon the result of Collier-Cartaino, Graber and Jiang who proved that for every fixed $r\ge 3$, $l\ge 4$, we have $R(C_l^r,K_n^r)=O(n^{1+1/(\lfloor l/2\rfloor -1)})$.

18 pages