Sharp transition of the invertibility of the adjacency matrices of sparse random graphs

We consider three models of sparse random graphs: undirected and directed Erdos-Renyi graphs and random bipartite graph with two equal parts. For such graphs, we show that if the edge connectivity probability p satisfies np >= log n + k(n) with k(n) -> infinity as n -> infinity, then the adjacency matrix is invertible with probability approaching one (n is the number of vertices in the two former cases and the same for each part in the latter case). For np <= log n -k(n) these matrices are invertible with probability approaching zero, as n -> infinity. In the intermediate region, when np = log n + k(n), for a bounded sequence k(n) is an element of R, the event Omega(0) that the adjacency matrix has a zero row or a column and its complement both have a non-vanishing probability. For such choices of p our results show that conditioned on the event Omega(c)(0) the matrices are again invertible with probability tending to one. This shows that the primary reason for the non-invertibility of such matrices is the existence of a zero row or a column. We further derive a bound on the (modified) condition number of these matrices on Omega(c)(0), with a large probability, establishing von Neumann's prediction about the condition number up to a factor of n(o(1)).