Ferber–McKinley–Samotij's conjecture on nontrivial extremal growth

About 4 years old · traced to

Let HH be a graph that is not a forest. Define its 2-density by

m2(H)=max⁡{e(F)−1v(F)−2:F⊆H, v(F)>2}.m_2(H)=\max\left\{\frac{e(F)-1}{v(F)-2}:F\subseteq H,\ v(F)>2\right\}.

Ferber–McKinley–Samotij's conjecture. There exists an ε>0\varepsilon>0 such that

ex⁡(n,H)≥εn2−1/m2(H)+ε.\operatorname{ex}(n,H)\geq \varepsilon n^{2-1/m_2(H)+\varepsilon}.

The conjecture expresses the belief that the elementary probabilistic lower bound is not asymptotically tight for graphs containing a cycle. The source presents it as open and uses this type of extremal-growth hypothesis in enumeration results.

References

Primary source

Tao Jiang and Sean Longbrake, “Balanced supersaturation and Turan numbers in random graphs”, arXiv:2208.10572 (2024).

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.