← All problems

Quadratic edge-statistics conjecture

7 years old · documented by

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

min⁡{ℓ,(k2)−ℓ}=Ω(k2),\min \left\{\ell, \binom{k}{2} - \ell \right\} = \Omega(k^2),

we have

ind⁡(k,ℓ)=O(k−1/2).\operatorname{ind}(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/2k^{-1/2}, but the asserted universal upper bound remains open.

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

Progress summary

Refreshed
Open · solution reported

The conjecture’s claimed upper bound was proved in 2018, and no later gap or reversal was found.

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 Ω(k)≤ℓ≤(k2)−Ω(k)\Omega(k)\leq \ell\leq \binom{k}{2}-\Omega(k), which includes the quadratic range.
  • A related 2018 paper established only ind⁡(k,ℓ)≤log⁡O(1)(ℓ∗/k)k/ℓ∗\operatorname{ind}(k,\ell)\leq \log^{O(1)}(\ell^*/k)\sqrt{k/\ell^*} in its stated theorem, with ℓ∗=min⁡{ℓ,(k2)−ℓ}\ell^*=\min\{\ell,\binom{k}{2}-\ell\}.
  • Examples attain order k−1/2k^{-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 ind⁡(k,ℓ)=O(k−1/2)\operatorname{ind}(k,\ell)=O(k^{-1/2}) is settled; no counterexample, proof gap, withdrawal, or retraction was found.

Sources

Solutions 0

No solutions have been posted yet.