Combinatorial anti-concentration inequalities, with applications

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.

References in corpus (3)

• A Completion of the Proof of the Edge-statistics Conjecture
• The edge-statistics conjecture for $\ell \ll k^{6/5}$
• A Local Limit Theorem for Cliques in G(n,p)

Cited by in corpus (5)

• Bernoulli sums and Rényi entropy inequalities
• An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
• Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture
• On Littlewood-Offord theory for arbitrary distributions
• On the permanent of a random symmetric matrix