printable pdf
比利时vs摩洛哥足彩 ,
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

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