On the singularity of random symmetric matrices

Combinatorics Seminar
Event time: 
Thursday, February 14, 2019 - 4:00pm
DL 431
Asaf Ferber
Speaker affiliation: 
Event description: 

Let $M_n$ be an $n\times n$ symmetric matrix with entries in $\pm 1$, chosen uniformly at random. It is widely conjectured that $M_n$ is singular with probability at most $(2+o(1))^{-n}$. On the other hand, the best known upper bound on the singularity probability of $M_n$, due to Vershynin (2011), is $2^{-n^c}$, for some unspecified small constant $c > 0$ (this improves on a polynomial bound due to Costello, Tao, and Vu (2005), and a bound of the form $n^{-\omega(1)}$due to Nguyen (2011) ).

In this talk, using a novel combinatorial approach, we show that the probability of singularity of $M_n$ is at most $2^{-n^{1/4}}$. We also discuss improvements for other models of discrete random matrices.

Joint work with Vishesh Jain

Research Area(s):