Counting odd cycles in sparse pseudorandom graphs

We answer two extremal questions about odd cycles that naturally arise in the study of sparse pseudorandom graphs. Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Gamma"> <mml:semantics> <mml:mi mathvariant="normal"> Γ </mml:mi> <mml:annotation encoding="application/x-tex">\Gamma</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis n comma d comma lamda right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>d</mml:mi> <mml:mo>,</mml:mo> <mml:mi> λ </mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(n,d,\lambda )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -graph, i.e., <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -vertex, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"> <mml:semantics> <mml:mi>d</mml:mi> <mml:annotation encoding="application/x-tex">d</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -regular graphs with all nontrivial eigenvalues in the interval <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-bracket negative lamda comma lamda right-bracket"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">[</mml:mo> <mml:mo> − </mml:mo> <mml:mi> λ </mml:mi> <mml:mo>,</mml:mo> <mml:mi> λ </mml:mi> <mml:mo stretchy="false">]</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">[-\lambda ,\lambda ]</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . Krivelevich, Lee, and Sudakov [SIAM J. Discrete Math. 24 (2010), pp. 1–16] conjectured that, whenever <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda Superscript 2 k minus 1 Baseline much-less-than d Superscript 2 k Baseline slash n"> <mml:semantics> <mml:mrow> <mml:msup> <mml:mi> λ </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo> ≪ </mml:mo> <mml:msup> <mml:mi>d</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> </mml:mrow> </mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\lambda ^{2k-1}\ll d^{2k}/n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , every subgraph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Gamma"> <mml:semantics> <mml:mi mathvariant="normal"> Γ </mml:mi> <mml:annotation encoding="application/x-tex">\Gamma</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis 1 slash 2 plus o left-parenthesis 1 right-parenthesis right-parenthesis e left-parenthesis normal upper Gamma right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> <mml:mi>e</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi mathvariant="normal"> Γ </mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(1/2+o(1))e(\Gamma )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> edges contains an odd cycle <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C Subscript 2 k plus 1"> <mml:semantics> <mml:msub> <mml:mi>C</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">C_{2k+1}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . Aigner-Horev, Hàn, and the third author [Combinatorica 34 (2014), pp. 379–406] proved a weaker statment by allowing an extra polylogarithmic factor in the assumption <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda Superscript 2 k minus 1 Baseline much-less-than d Superscript 2 k Baseline slash n">