1/e upper bound on ind(k,ℓ)

Conjecture 1.1 (The Edge-statistics Conjecture) · arXiv:1805.06848

arXiv Conjecture high confidence— first stated 2019-11-01

Authors: Noga Alon, Dan Hefetz, Michael Krivelevich, Mykhaylo Tyomkyn

Status solved high confidence

The Edge-statistics Conjecture was fully resolved within months of its arXiv posting. Kwan, Sudakov and Tran (arXiv:1807.05202) proved the conjecture for the range Ω(k) ≤ ℓ ≤ binom(k,2)/2, and Fox and Sauermann (arXiv:1809.01352, Advances in Combinatorics 2020:4) completed the proof by handling the remaining case 1 ≤ ℓ ≤ C·k; Martinsson, Mousset, Noever and Trujić independently covered the sublinear regime ℓ ≪ k^{6/5}. The hypergraph generalisation suggested in the original paper was subsequently proved by Jain, Kwan, Mubayi and Tran (arXiv:2505.03954, IMRN 2025).

Cited literature (3)

partial Anticoncentration for subgraph statistics (2018)

Matthew Kwan, Benny Sudakov, Tuan Tran · arXiv preprint · arXiv:1807.05202

Proves the Edge-statistics Conjecture for the linear range Ω(k) ≤ ℓ ≤ binom(k,2)/2, establishing ind(k,ℓ) ≤ log^{O(1)}(ℓ*/k) · sqrt(k/ℓ*) where ℓ* = min{ℓ, binom(k,2) − ℓ}.
proof A Completion of the Proof of the Edge-statistics Conjecture (2020)

Jacob Fox, Lisa Sauermann · Advances in Combinatorics, 2020:4 · arXiv:1809.01352

Completes the full proof of the conjecture by handling the remaining case 1 ≤ ℓ ≤ C·k (Theorem 1.2), together with Kwan–Sudakov–Tran which covered C·k ≤ ℓ ≤ binom(k,2)/2, establishing ind(k,ℓ) ≤ 1/e + o_k(1) for all 0 < ℓ < binom(k,2).
proof The edge-statistics conjecture for hypergraphs (2025)

Vishesh Jain, Matthew Kwan, Dhruv Mubayi, Tuan Tran · International Mathematics Research Notices, 2025:18 · arXiv:2505.03954

Proves the hypergraph generalisation of the conjecture suggested by Alon–Hefetz–Krivelevich–Tyomkyn: for r-uniform hypergraphs the fraction of k-vertex subsets spanning exactly ℓ edges is at most 1/e + ε for k sufficiently large whenever ℓ is neither 0 nor maximal.

Reviewer notes. Martinsson, Mousset, Noever and Trujić (arXiv:1809.02576, Israel Journal of Mathematics) independently proved the conjecture for ℓ ≪ k^{6/5}; their paper appeared in search results but was not WebFetched, so it is noted here rather than included in since_posted. The Fox–Sauermann paper (1809.01352) is the canonical completion cited in the literature, with the Kwan–Sudakov–Tran paper covering the complementary linear range.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every $\varepsilon > 0$ there exists $k_0 = k_0(\varepsilon)$ such that for all integers $k > k_0$ and $0 < \ell < \binom{k}{2}$ we have $\mathrm{ind}(k, \ell) \leq 1/e + \varepsilon$.

Context

The authors observe that the random graph $G(n,p)$ with $p = \binom{k}{2}^{-1}$ gives $\mathrm{ind}(k,1) \geq 1/e + o_k(1)$, and that the complete bipartite graph with smaller part of size $n/k$ achieves the same asymptotic lower bound for $\ell = k-1$. These constructions, together with additional data, motivate the conjecture that $1/e$ is an asymptotically tight upper bound for every non-trivial $\ell$.

Source paper

Edge-statistics on large graphs
Noga Alon, Dan Hefetz, Michael Krivelevich, Mykhaylo Tyomkyn · 2019-11-01
https://arxiv.org/abs/1805.06848 PDF source