Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, October 30, 2018 - 3:00pm

Anirban Basak

Weizmann

Location

Temple University

Wachman Hall 617

Note the location change

Consider an $n \times n$ matrix with i.i.d.~Bernoulli($p$) entries. It is well known that for $p= \Omega(1)$, i.e.~$p$ is bounded below by some positive constant, the matrix is invertible with high probability. If $p \ll \frac{\log n}{n}$ then the matrix contains zero rows and columns with high probability and hence it is singular with high probability. In this talk, we will discuss the sharp transition of the invertibility of this matrix at $p =\frac{\log n}{n}$. This phenomenon extends to the adjacency matrices of directed and undirected Erd\H{o}s-R\'{e}nyi graphs, and random bipartite graph. 
 
Joint work with Mark Rudelson.