Erd s–Simonovits even-cycle extremal-number conjecture

At least 12 years old · documented by

Let ℓ⩾2\ell\geqslant2, and write

ex⁡(n,{C3,C4,…,C2ℓ})\operatorname{ex}\bigl(n,\{C_3,C_4,\ldots,C_{2\ell}\}\bigr)

for the maximum number of edges in an nn-vertex graph containing none of the cycles C3,C4,…,C2ℓC_3,C_4,\ldots,C_{2\ell}. Erd s–Simonovits conjecture.

ex⁡(n,{C3,C4,…,C2ℓ})=Θ(n1+1/ℓ).\operatorname{ex}\bigl(n,\{C_3,C_4,\ldots,C_{2\ell}\}\bigr)=\Theta\bigl(n^{1+1/\ell}\bigr).

The source invokes this conjecture conditionally to show that the bounds of its random Tur n theorem are essentially best possible.

References

Primary source

Robert Morris and David Saxton, “The number of C_2l-free graphs”, arXiv:1309.2927 (2015).

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.