The Ramsey threshold for trees versus odd cycles

Abstract

A longstanding fundamental problem of Burr, Erdős, Faudree, Rousseau and Schelp (\emph{Trans. Amer. Math. Soc.}, 1982) is to determine the exact value of the least integer $f(m)$, for odd $m\ge 3$, such that every tree $T_n$ on $n\ge f(m)$ vertices satisfies $R(T_n,C_m)=2n-1$. We settle this problem for all sufficiently large odd $m$. Indeed, we establish $$f(m)=\lceil \frac{2m-1}{3}\rceil$$ for all such $m$, where the lower bound follows from a result by Faudree, Lawrence, Parsons and Schelp. This also confirms a conjecture of Huang, Zhang and Chen for all such $m$.

arXiv commentIn this version, we've made some minor adjustments to the details