Odd cycles in subgraphs of sparse pseudorandom graphs

Abstract

We answer two extremal questions about odd cycles that naturally arise in the study of sparse pseudorandom graphs. Let $\Gamma$ be an $(n,d,\lambda )$-graph, i.e., $n$-vertex, $d$-regular graphs with all nontrivial eigenvalues in the interval $[-\lambda ,\lambda ]$. Krivelevich, Lee, and Sudakov conjectured that, whenever ${\lambda }^{2k-1}\ll d^{2k}/n$, every subgraph $G$ of $\Gamma$ with $(1/2+o(1))e(\Gamma )$ edges contains an odd cycle $C_{2k+1}$. Aigner-Horev, Hàn, and the third author proved a weaker statement by allowing an extra polylogarithmic factor in the assumption ${\lambda }^{2k-1}\ll d^{2k}/n$, but we completely remove it and hence settle the conjecture. This also generalises Sudakov, Szabo, and Vu's Turán-type theorem for triangles. Secondly, we obtain a Ramsey multiplicity result for odd cycles. Namely, in the same range of parameters, we prove that every 2-edge-colouring of $\Gamma$ contains at least $(1-o(1))2^{-2k}{d}^{2k+1}$ monochromatic copies of $C_{2k+1}$. Both results are asymptotically best possible by Alon and Kahale's construction of $C_{2k+1}$-free pseudorandom graphs.