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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. Erdős: On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898–902.
P. Erdős: Extremal problems in number theory, 1965, Proc. Sympos. Pure Math., Vol. VIII pp. 181–189 Amer. Math. Soc., Providence, R.I.
P. Frankl and Z. Füredi: Solution of the Littlewood-Offord problem in high dimensions, Ann. of Math. 128(2) (1988), 259–270.
J. Griggs, J. Lagarias, A. Odlyzko and J. Shearer: On the tightest packing of sums of vectors, European J. Combin. 4(3) (1983), 231–236.
G. Halász: Estimates for the concentration function of combinatorial number theory and probability, Period. Math. Hungar. 8(3–4) (1977), 197–211.
G. Katona: On a conjecture of Erdős and a stronger form of Sperner’s theorem, Studia Sci. Math. Hungar. 1 (1966), 59–63.
D. Kleitman: On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors, Advances in Math. 5 (1970), 155–157.
D. Kleitman: Some new results on the Littlewood-Offord problem, J. Combinatorial Theory Ser. A 20(1) (1976), 89–113.
D. Kleitman: On a lemma of Littlewood and Offord on the distribution of certain sums, Math. Z. 90 (1965), 251–259.
J. E. Littlewood and A. C. Offord: On the number of real roots of a random algebraic equation, III, Rec. Math. [Mat. Sbornik] N.S. 12 (1943), 277–286.
A. Sali: Strong from of an M-part Sperner theorem, European J. Combinatorics 4 (1983), 179–183.
A. Sali: A Sperner type theorem, Order 2 (1985), 123–127.
T. Tao and V. Vu: Inverse Littlewood-Offord theorems and the condition number of random matrices, Annals of Mathematics 2(169) (2009), 595–632.
T. Tao and V. Vu: Additive Combinatorics, Cambridge Univ. Press, 2006.
Author information
Authors and Affiliations
Corresponding author
Additional information
T. Tao is supported by NSF Research Award DMS-0649473, the NSFWaterman award and a grant from the MacArthur Foundation.
V. Vu is supported by research grants DMS-0901216 and AFOSAR-FA-9550-09-1-0167.
Rights and permissions
About this article
Cite this article
Tao, T., Vu, V. The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi. Combinatorica 32, 363–372 (2012). https://doi.org/10.1007/s00493-012-2716-x
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-012-2716-x