The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi

Abstract

We give a new bound on the probability that the random sum ξ 1 v 1+…+ξ n v n belongs to a ball of fixed radius, where the ξ i are i.i.d. Bernoulli random variables and the v i are vectors in R d . As an application, we prove a conjecture of Frankl and Füredi (raised in 1988), which can be seen as the high dimensional version of the classical Littlewood-Offord-Erdős theorem.

Locations

• COMBINATORICA - View
• arXiv (Cornell University) - View - PDF
• arXiv (Cornell University) - PDF
• COMBINATORICA - View
• arXiv (Cornell University) - View - PDF
• arXiv (Cornell University) - PDF