Singularity of random symmetric matrices -- a combinatorial approach to improved bounds

Understand

Let $M_n$ denote a random symmetric $n \times n$ matrix whose upper diagonal entries are independent and identically distributed Bernoulli random variables (which take values $1$ and $-1$ with probability $1/2$ each).

• 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 singularity bound due to Costello, Tao, and Vu (2005), and a bound of Nguyen (2011) showing that the singularity probability decays faster than any polynomial.