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

About 7 years old · traced to

Let GG be an nn-vertex graph. For 0≤k≤n0\leq k\leq n, choose a uniformly random kk-vertex subset A⊆V(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 k→∞k\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.

References

Primary source

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

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.