Alon–Hefetz–Krivelevich–Tyomkyn Poisson anti-concentration conjecture for graph edge statistics
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.
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
Sign in to submit a solution.
No solutions have been posted yet.