Super-linear edge-statistics conjecture

About 8 years old · traced to

Let ind⁡(k,ℓ)\operatorname{ind}(k,\ell) denote the limiting maximum proportion of kk-vertex subsets inducing exactly ℓ\ell edges. Super-linear edge-statistics conjecture. For all pairs (k,ℓ)(k,\ell) satisfying

min⁡{ℓ,(k2)−ℓ}=ω(k),\min \left\{\ell, \binom{k}{2} - \ell \right\} = \omega(k),

we have

ind⁡(k,ℓ)=o(1).\operatorname{ind}(k,\ell) = o(1).

The paper proves the analogous assertion when both edge counts are quadratic in kk and proposes replacing “quadratic” by “super-linear.” This strengthening remains open.

References

Primary source

Noga Alon, Dan Hefetz, Michael Krivelevich and Mykhaylo Tyomkyn, “Edge-statistics on large graphs”, arXiv:1805.06848 (2019).

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.