The exact generalized Turán number for \(C_6\) in \(C_8\)-free graphs

Abstract

For graphs $F$ and $H$, let $\ex(n,F,H)$ denote the maximum number of copies of $F$ in an $n$-vertex $H$-free graph. Gerbner, Győri, Methuku and Vizer proved that $\ex(n,C_6,C_8)=Θ(n^3)$ and predicted that the unrestricted problem should have the same first-order asymptotics as the bipartite one. We determine the exact value for all sufficiently large $n$, showing that \[ \ex(n,C_6,C_8)=6\binom{n-3}{3}+12(n-5). \] Moreover, the unique extremal graph is $K_3\vee (K_2\cup I_{n-5})$. The main new ingredient is a codegree decomposition for $C_8$-free graphs: a packing lemma for triangles in the linear-codegree graph recovers an almost spanning common neighborhood, and a defect-absorption argument upgrades this stability to the exact extremal graph.

14pages