Alon–Hefetz–Krivelevich–Tyomkyn Poisson anti-concentration conjecture for graph edge statistics

From papers

Let GG be an nn-vertex graph. For 0kn0\leq k\leq n, choose a uniformly random kk-vertex subset AV(G)A\subseteq V(G) and let XG,k:=e(G[A])X_{G,k}:=e(G[A]) be the number of edges induced by AA. Suppose kk\to\infty and nn grows sufficiently rapidly in terms of kk. For every integer \ell with

0<<(k2),0<\ell<\binom{k}{2},

Alon–Hefetz–Krivelevich–Tyomkyn's conjecture. One has

Pr(XG,k=)1/e+o(1).\Pr(X_{G,k}=\ell)\leq 1/e+o(1).

This conjecture seeks a Poisson-type universal upper bound, analogous to the maximum point mass of a Poisson random variable with mean one. The source gives no resolution, so the conjecture remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Jacob Fox, Matthew Kwan and Lisa Sauermann, “Combinatorial anti-concentration inequalities, with applications”, arXiv:1905.12142 (2020).

Solutions 0

No solutions have been posted yet.