The edge-statistics conjecture for $\ell \ll k^{6/5}$

Abstract

Let $k$ and $\ell$ be positive integers. We prove that if $1\le \ell \le o_k(k^{6/5})$, then in every large enough graph $G$, the fraction of $k$-vertex subsets that induce exactly $\ell$ edges is at most $1/e+o_k(1)$. Together with a recent result of Kwan, Sudakov, and Tran, this settles a conjecture of Alon, Hefetz, Krivelevich, and Tyomkyn.

8 pages; published version

References in corpus (1)

• A Completion of the Proof of the Edge-statistics Conjecture

Cited by in corpus (2)

• Combinatorial anti-concentration inequalities, with applications
• An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs