Alon–Hefetz–Krivelevich–Tyomkyn Poisson anti-concentration conjecture for graph edge statistics
Let be an -vertex graph. For , choose a uniformly random -vertex subset and let be the number of edges induced by . Suppose and grows sufficiently rapidly in terms of . For every integer with
Alon–Hefetz–Krivelevich–Tyomkyn's conjecture. One has
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
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.