Alon–Hefetz–Krivelevich–Tyomkyn quadratic-range edge-statistics conjecture

About 8 years old · traced to

For a graph GG, let XG,kX_{G,k} be the number of edges induced by a uniformly random kk-vertex subset, and define

I(n,k,ℓ):=max⁡{P[XG,k=ℓ]:v(G)=n},I(n,k,\ell):=\max\{\mathbb{P}[X_{G,k}=\ell]:v(G)=n\},

with

ind⁡(k,ℓ):=lim⁡n→∞I(n,k,ℓ).\operatorname{ind}(k,\ell):=\lim_{n\to\infty}I(n,k,\ell).

Quadratic-range edge-statistics conjecture. For all k,ℓ∈Nk,\ell\in\mathbb{N} with

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

we have

ind⁡(k,ℓ)=Ok(k−1/2).\operatorname{ind}(k,\ell)=O_k(k^{-1/2}).

This is a quantitative strengthening in the dense interior range of the edge-count parameter, predicting a polynomial decay of the maximum asymptotic fraction of kk-vertex subsets inducing exactly ℓ\ell edges. The supplied text does not state whether this conjecture has been resolved.

References

Primary source

Anders Martinsson, Frank Mousset, Andreas Noever and Miloš Trujić, “The edge-statistics conjecture for k^6/5”, arXiv:1809.02576 (2021).

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.