Applications of Random graphs part1(Machine Learning)

Abstract: Two landmark results in combinatorial random matrix theory, due to Komlós and Costello-Tao-Vu, show that discrete random matrices and symmetric discrete random matrices are typically nonsingular. In particular, in the language of graph theory, when p is a fixed constant, the biadjacency matrix of a random Erdős-Rényi bipartite graph G(n,n,p) and the adjacency matrix of an Erdős-Rényi random graph G(n,p) are both nonsingular with high probability. However, very sparse random graphs (i.e., where p is allowed to decay rapidly with n) are typically singular, due to the presence of "local" dependencies such as isolated vertices and pairs of degree-1 vertices with the same neighbour. In this paper we give a combinatorial description of the rank of a sparse random graph G(n,n,c/n) or G(n,c/n) in terms of such local dependencies, for all constants c e (and we present some evidence that the situation is very different for c e). This gives an essentially complete answer to a question raised by Vu at the 2014 International Congress of Mathematicians.