Departmental Colloquium
Bhargav Narayanan
Rutgers
Anticoncentration and Antichain Codes
Abstract: A basic problem at the intersection of probability and combinatorics is the Littlewood-Offord anti
concentration problem: given real numbers a_1, ... , a_n, what is the largest possible point probability
of the random sum a_1 X_1 +... + a_n X_n for iid Bernoulli random variables X_1, ... , X_n?
Several variants of this problem, involving additional arithmetic constraints on the numbers
a_1, ... , a_n, have proved to both be deep and widely applicable; two notable examples of such
variants include the Sarkozy-Szemeredi theorem (resolving the Erdos-Moser problem) and Halasz's
theorem. A few years ago, it became evident to me that all of these arithmetic results are in fact
specialisations of a more abstract, purely combinatorial phenomenon. In this talk, I will take the scenic
route to the recent proof of such an abstract result, regarding the density of “antichain codes” in the
Boolean hypercube, surveying the history of these problems and some of the many applications
along the way.
Note the unusual time!
Friday November 18, 2022 at 2:00 PM in 636 SEO