Probability and Mathematical Physics Seminar

---

Sharp transition of invertibility of sparse random matrices

Speaker: Anirban Basak, ICTS-TIFR

Location: Warren Weaver Hall 512

Date: Friday, October 19, 2018, 11 a.m.

Synopsis:

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ős–Rényi graphs, and random bipartite graph.

Joint work with Mark Rudelson.