Extremal results for odd cycles in sparse pseudorandom graphs

Abstract

We consider extremal problems for subgraphs of pseudorandom graphs. For graphs $F$ and $\Gamma$ the generalized Turán density ${\pi }_F(\Gamma )$ denotes the density of a maximum subgraph of $\Gamma$, which contains no copy of~$F$. Extending classical Turán type results for odd cycles, we show that ${\pi }_F(\Gamma )=1/2$ provided $F$ is an odd cycle and $\Gamma$ is a sufficiently pseudorandom graph. In particular, for $(n,d,\lambda )$-graphs $\Gamma$, i.e., $n$-vertex, $d$-regular graphs with all non-trivial eigenvalues in the interval $[-\lambda ,\lambda ]$, our result holds for odd cycles of length $\ell$, provided \[ λ^{\ell-2}\ll \frac{d^{\ell-1}}n\log(n)^{-(\ell-2)(\ell-3)}\,. \] Up to the polylog-factor this verifies a conjecture of Krivelevich, Lee, and Sudakov. For triangles the condition is best possible and was proven previously by Sudakov, Szabó, and Vu, who addressed the case when $F$ is a complete graph. A construction of Alon and Kahale (based on an earlier construction of Alon for triangle-free $(n,d,\lambda )$-graphs) shows that our assumption on $\Gamma$ is best possible up to the polylog-factor for every odd $\ell \ge 5$.