Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Combinatorics Seminar

Asaf Ferber

MIT

When combinatorics meets Littlewood-Offord theory

Abstract:

Given an integer vector $a = (a_1,\dots,a_n)$, let $\rho(a)$ be the number of solutions to $a\cdot x=0$, with $x\in \{\pm 1\}^n$. In 1945, Erdos gave a beautiful combinatorial solution to the following problem that was posed by Littlewood and Offord: how large can $\rho(a)$ be if all the entries of $a$ are non-zero? Following his breakthrough result, several extensions of this problem have been intensively studied by various researchers. In classical works, Erdos-Moser, Sarkozy-Szemeredi, and Halasz obtained better bounds on $\rho(a)$ under additional assumptions on $a$, while Kleitman, Frankl-Furedi, Esseen, Halasz and many others studied generalizations to higher dimensions. In recent years, motivated by deep Freiman-type inverse theorems from additive combinatorics, Tao and Vu brought a new view to this problem by asking for the underlying structural reason for $\rho(a)$ to be large --this is known as the Inverse Littlewood-Offord problem, which is a cornerstone of modern random matrix theory. In this talk, we will discuss further extensions and improvements for both forward and inverse Littlewood-Offord problems where combinatorial tools and insights have proved to be especially powerful. We also present several applications in (discrete) matrix theory such as: a non-trivial upper bound on the number of Hadamard matrices, an upper bound on the number of $\pm 1$ normal matrices (improving a result of Deneanu and Vu), and a unified approach for counting the number of singular $\pm1$ matrices from various popular models (improving results of Cook, Nguyen and Vershynin).

Host: Jacques Verstraete

January 10, 2019

2:00 PM

AP&M 6402

****************************