We consider extremal problems for subgraphs of pseudorandom graphs. For graphs $F$ and $Gamma$ the generalized Turan density $pi_F(Gamma)$ denotes the density of a maximum subgraph of $Gamma$, which contains no copy of~$F$. Extending classical Turan 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 [ lambda^{ell-2}ll frac{d^{ell-1}}nlog(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, Szabo, 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 $ellgeq 5$.
Download