Erdős Problem #572 — Extremal numbers of even cycles
For a positive integer , let be the maximum number of edges in a simple graph on vertices containing no subgraph isomorphic to the cycle of length . The question is whether, for every fixed integer , there are constants and such that
for every integer . Equivalently, the requested lower bound is , with the implicit positive constant allowed to depend on fixed . Erdős Problems #572 Pikhurko (2012)
Background
Even-cycle extremal questions are a central part of degenerate extremal graph theory: forbidding a bipartite graph leads to a substantially different problem from forbidding a non-bipartite one. The study of even cycles goes back at least to Erdős’s 1938 work; the four-cycle case is much better understood, with . Erdős and Simonovits conjectured the exponent for every fixed even cycle, while constructions for and show that the simple conjecture for the leading constant, , does not hold in general. Pikhurko (2012) Füredi and Simonovits (2013)
The matching upper exponent is known: Erdős and Bondy–Simonovits established an upper bound of order , and Pikhurko later proved, for all integers and ,
Thus the question asks whether this exponent is attained from below, not whether it is an upper bound. Erdős Problems #572 Pikhurko (2012)
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.