The exact generalized Tur\'an number for \(C_6\) in \(C_8\)-free graphs

Summary · qwen2.5:32b

The study determines the exact value of \(\ex(n,C_6,C_8)\) as \(6\binom{n-3}{3}+12(n-5)\) for sufficiently large \(n\), confirming Gerbner et al.'s prediction on asymptotics; the unique extremal graph is identified as \(K_3\vee (K_2\cup I_{n-5})\).

Suggested post angle

This new research in graph theory could have interesting implications for graphics algorithms and optimization!

Excerpt

arXiv:2607.03856v1 Announce Type: new 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\H{o}ri, Methuku and Vizer proved that $\ex(n,C_6,C_8)=\Theta(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.