Document Type
Lecture
Publication Date
10-29-2014
Abstract
The classical Littlewood-Offord problem is a combinatorial question in geometry that asks for the maximum number subsums of vectors v1 vn Rd of length at least 1 that fall into a xed set A Rd. Erdos proved that the best upper bound in the case d = 1 and A = (xx+2] is n n 2 using Sperners theorem. The problem has a very natural probabilistic formulation. Consider n independent random variables i such that P( i = 1) = 1 2 and let ai 1. Then sup ai x P(a1 1 + +an n (xx+2])=P( 1+ + n ( 11]) In this talk I shall discuss a strong generalization of the latter inequality for arbitrary random variables with only information about their local concentration provided. In particular, a proof of a question posed by Leader and Radcli e will be presented. One of the main ingredients of the proof will be a Sperner type theorem for multisets. Even in the case for sets the proof is new and very elementary.
Relational Format
presentation
Recommended Citation
Juskevicius, Tomas, "On a conjecture of Leader and Radcliffe related to the Littlewood-Offord problem" (2014). Combinatorics Seminar. 47.
https://egrove.olemiss.edu/math_combinatorics/47