Even-cycle Turán lower bound: is $\mathrm{ex}(n;C_{2k})\gg n^{1+1/k}$ for every $k\geq 3$? (Erdős #572)
Statement
For a graph $H$, let $\mathrm{ex}(n;H)$ be the Turán number: the maximum number of edges in an $n$-vertex graph containing no copy of $H$. Let $C_{2k}$ denote the cycle of length $2k$. Conjecture (Erdős): for every fixed $k\geq 3$, $$\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{1}{k}},$$ i.e. there exist $C_{2k}$-free graphs on $n$ vertices with at least $c_k\,n^{1+1/k}$ edges for some constant $c_k>0$ and all large $n$. Together with the known matching upper bound this would give $\mathrm{ex}(n;C_{2k})\asymp n^{1+1/k}$.
Acceptance. FULLY RESOLVES: a complete proof that $\mathrm{ex}(n;C_{2k})\gg n^{1+1/k}$ for all $k\geq 3$ — a construction of $C_{2k}$-free graphs achieving $\gg n^{1+1/k}$ edges with a proof of both the $C_{2k}$-freeness and the edge count — OR a disproof: a proof that for some $k$ no such dense family exists. Machine-checkable proof preferred, else a full written proof with all steps. ADVANCES, each with proof or machine-checkable certificate: prove the conjectured lower bound $\gg n^{1+1/k}$ for a NEW value of $k$ beyond the known $k\in\{2,3,5\}$ (e.g. $k=4$); OR improve the general lower-bound exponent strictly beyond the best stated in the background, the Lazebnik–Ustimenko–Woldar exponent $1+\frac{2}{3k-3+\nu}$, for some $k$, via a construction with proof; OR extend the record of dense $C_{2k}$-free graphs for small $n$ with a reproducible construction plus a machine-checkable certificate of $C_{2k}$-freeness and the edge count. Deliver the graph construction (or family) with proof of girth and edge count, or the improved-exponent theorem with its proof.
Background
The even-cycle Turán problem. Odd cycles are easy: $\mathrm{ex}(n;C_{2k+1})=\lfloor n^2/4\rfloor$ for $n>2k+1$, since a balanced complete bipartite graph is $C_{2k+1}$-free. The even case is hard. Erdős and Klein [Er38] proved $\mathrm{ex}(n;C_4)\asymp n^{3/2}$. The upper-bound side is fully settled: Erdős [Er64c], and Bondy and Simonovits [BoSi74], proved $\mathrm{ex}(n;C_{2k})\ll k\,n^{1+1/k}$ for all $k$. The conjectured matching LOWER bound $\gg n^{1+1/k}$ is known only for $k=2$ (via $C_4$) and, by Benson's [Be66] generalized-polygon constructions, for $k=3$ and $k=5$ (yielding $\mathrm{ex}(n;C_6)\asymp n^{4/3}$ and $\mathrm{ex}(n;C_{10})\asymp n^{6/5}$); it is OPEN for every other $k$, notably $k=4$. The best general lower bound is due to Lazebnik, Ustimenko, and Woldar [LUW95]: $\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{2}{3k-3+\nu}}$, with $\nu=0$ for odd $k$ and $\nu=1$ for even $k$ — an exponent strictly below the conjectured $1+1/k$. See [LUW99] for further history; related is Erdős #765 (erdosproblems.com/765); this is #46 in the Extremal Graph Theory problem collection. Listed as open on erdosproblems.com/572 (fetched 2026-07-13, status 'open'), tagged graph theory | turan number | cycles. Attacker's tool: explicit algebraic constructions of dense high-girth graphs (generalized polygons, incidence graphs of geometries, Lazebnik–Ustimenko-type algebraic/Cayley families) plus computer search for dense $C_{2k}$-free graphs on small $n$ — checking $C_{2k}$-freeness and counting edges is a finite computation, giving genuine purchase on new constructions and record configurations.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #572 (T. F. Bloom) | website |
| REF-02 | Extremal Graph Theory collection #46 — even-cycle Turán lower bound | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.