The Combinatorics of Discrete Random Matrices

In random matrix theory, both continuous random matrix ensembles (e.g. the gaussian unitary ensemble, GUE) and discrete random matrix ensembles (e.g. the Bernoulli ensemble of random sign matrices, or the adjacency matrices of random graphs) are of interest. However, the discrete case contains additional difficulties that are not present in the continuous case. For instance, it is obvious that continuous random square matrices are almost surely invertible, but this is not true in the discrete case. Nevertheless, in recent years several tools of an additive combinatorics nature have been developed to close the gap between our understanding of discrete random matrices and continuous random matrices, and in particular $/inverse Littlewood-Offord theory/$, which roughly speaking asserts that discrete random walks behave much like their continuous counterparts, except in highly arithmetically structured cases, such as when the step sizes of the random walk all lie in an arithmetic progression. We survey these developments, and their applications, in this talk.

Terence Tao, University of California, Los Angeles

Renew SIAM · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube