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

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,):=limnI(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(k1/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.

Sources & referencesView supporting material

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.