Article contents
Combinatorial anti-concentration inequalities, with applications
Published online by Cambridge University Press: 30 June 2021
Abstract
We prove several different anti-concentration inequalities for functions of independent Bernoulli-distributed random variables. First, motivated by a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn, we prove some “Poisson-type” anti-concentration theorems that give bounds of the form 1/e + o(1) for the point probabilities of certain polynomials. Second, we prove an anti-concentration inequality for polynomials with nonnegative coefficients which extends the classical Erdős–Littlewood–Offord theorem and improves a theorem of Meka, Nguyen and Vu for polynomials of this type. As an application, we prove some new anti-concentration bounds for subgraph counts in random graphs.
MSC classification
- Type
- Research Article
- Information
- Mathematical Proceedings of the Cambridge Philosophical Society , Volume 171 , Issue 2 , September 2021 , pp. 227 - 248
- Copyright
- © The Author(s), 2021. Published by Cambridge University Press on behalf of Cambridge Philosophical Society
Footnotes
Research supported by a Packard Fellowship and by NSF Award DMS-1855635.
Research supported in part by SNSF project 178493.
References
REFERENCES
- 6
- Cited by