Even-cycle Turán number
Bondy–Murty, Graph Theory, Appendix A, item 34 · Extremal problems
Status partial high confidence
The conjecture that ex(n, C_{2k}) >= c * n^{1+1/k} for all k >= 2 remains open in general. The lower bound is established only for k = 2 (via polarity graphs giving Theta(n^{3/2})), k = 3 (incidence graphs of projective planes giving Theta(n^{4/3})), and k = 5 (related to generalized hexagons, giving Theta(n^{6/5})). For all other k, the best known general lower bound is the Lazebnik–Ustimenko–Woldar construction (1995) yielding ex(n, C_{2k}) >= c * n^{1 + 2/(3k-3)}, which falls short of the conjectured n^{1+1/k}. No recent breakthrough resolving the conjecture for all k was found in a thorough search through 2026.
Reviewer notes. The Bondy–Murty statement is the weak form: existence of some constant c > 0 (not the exact constant 1/2 conjectured by Erdős–Simonovits). The three known cases (k=2,3,5) arise from classical algebraic constructions via finite geometry (polarity graphs, incidence graphs of finite projective planes, generalized hexagons / Wenger graphs). For general k, the Lazebnik–Ustimenko–Woldar 1995 construction yields ex(n, C_{2k}) >= c * n^{1+2/(3k-3)}, which is the best known general lower bound but weaker than n^{1+1/k} for k >= 4. The OPG record 'turan_number_of_a_finite_family' and erdosproblems.com item 572 both track this problem; the erdosproblems.com page returned HTTP 403 and could not be verified directly. Checked arXiv preprints 2211.02015, 2411.01782, and 2506.09020 — none address this conjecture. The Springer Combinatorica paper 'On a conjecture of Erdős and Simonovits: Even cycles' (Keevash, 2013) was found in search results but not fetched; from context it does not resolve the general case. No resolution for all k >= 2 was found as of September 2026.
Context
$\mathrm{ex}(n, C_{2k})$ is the maximum number of edges of a simple graph on $n$ vertices with no cycle of length $2k$; the Bondy–Simonovits theorem gives the matching upper bound $O(n^{1+1/k})$. Known for $k = 2, 3, 5$.
In the book: Exercise 12.2.14.
Related records in this index
This conjecture was absent from the Open Problem Garden and arXiv corpora; the records below are the nearest ones.
- Turán number of a finite family. — discusses the even-cycle case
- erdosproblems.com #572 — same statement
Source
Théorie des graphes (J.A. Bondy, U.S.R. Murty; French edition by Frédéric Havet, 2025), Appendix A « Problèmes ouverts »
Item 34, book p. 629 (PDF p. 645) ·
https://inria.hal.science/hal-05211979v1 ·
PDF
English edition: J.A. Bondy, U.S.R. Murty, Graph Theory, GTM 244, Springer 2008, Appendix A.