Let operatornameind(k,ell) denote the limiting maximum proportion of k-vertex subsets inducing exactly ell edges. Quadratic edge-statistics conjecture. For all pairs (k,ell) satisfying min ell, binomk2 - ell = Omega(k^2), we have operatornameind(k,ell) = O(k^-1/2). The conjecture concerns the correct order in the dense edge-count range. The paper notes examples with a matching lower bound of order k^-1/2, but the asserted universal upper bound remains open.

Quadratic edge-statistics conjecture

The assertion appears in the 2018 literature as the dense-range part of the broader edge-statistics conjecture, attributed to Alon, Hefetz, Krivelevich, and Tyomkyn. The dense regime is now covered by published or publicly available proofs.

Known results

Kwan, Sudakov, and Tran (2018) proved the bound for $\Omega(k)\leq \ell\leq \binom{k}{2}-\Omega(k)$ , which includes the quadratic range.
A related 2018 paper established only $\operatorname{ind}(k,\ell)\leq \log^{O(1)}(\ell^*/k)\sqrt{k/\ell^*}$ in its stated theorem, with $\ell^*=\min\{\ell,\binom{k}{2}-\ell\}$ .
Examples attain order $k^{-1/2}$ in some cases, showing the dense bound has the correct order.

2018 completion of the edge-statistics conjecture

The completion paper explicitly states that Kwan, Sudakov, and Tran proved the linear-to-co-linear range; combined with independent sparse-regime results, this settles the full edge-statistics conjecture and therefore the quadratic edge-statistics conjecture.

Current status (as of August 2026): The quadratic dense-range bound $\operatorname{ind}(k,\ell)=O(k^{-1/2})$ is settled; no counterexample, proof gap, withdrawal, or retraction was found.

Quadratic edge-statistics conjecture

Primary source

Progress summary

Solutions 0