← All problems

Erdős Problem #572 — Extremal numbers of even cycles

62 years old · traced to

For a positive integer nn, let ex(n;C2k)\mathrm{ex}(n;C_{2k}) be the maximum number of edges in a simple graph on nn vertices containing no subgraph isomorphic to the cycle C2kC_{2k} of length 2k2k. The question is whether, for every fixed integer k≥3k\geq 3, there are constants ck>0c_k>0 and n0(k)n_0(k) such that

ex(n;C2k)≥ckn1+1/k\mathrm{ex}(n;C_{2k})\geq c_k n^{1+1/k}

for every integer n≥n0(k)n\geq n_0(k). Equivalently, the requested lower bound is ex(n;C2k)≫n1+1/k\mathrm{ex}(n;C_{2k})\gg n^{1+1/k}, with the implicit positive constant allowed to depend on fixed kk. 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 ex(n;C4)=Θ(n3/2)\mathrm{ex}(n;C_4)=\Theta(n^{3/2}). Erdős and Simonovits conjectured the exponent 1+1/k1+1/k for every fixed even cycle, while constructions for C6C_6 and C10C_{10} show that the simple conjecture for the leading constant, 12n1+1/k\tfrac12 n^{1+1/k}, 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 kn1+1/kk n^{1+1/k}, and Pikhurko later proved, for all integers k≥2k\geq2 and n≥1n\geq1,

ex(n;C2k)≤(k−1)n1+1/k+16(k−1)n.\mathrm{ex}(n;C_{2k})\leq (k-1)n^{1+1/k}+16(k-1)n.

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

Progress summary

Never refreshed

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.