Atlantic Graph Theory Seminar: Jane (Pu) Gao, University of Waterloo

Conditions for perfect matchings in random sparse bipartite graphs

Given a uniformly random sparse matrix A, with specified number of nonzero entries in columns and rows, we determine when A has full row rank over a finite field. As a corollary, by considering A as the adjacency matrix of a bipartite graph, our result determines the conditions for the existence of a perfect matching in various models of random sparse bipartite graphs. We will explore some useful insight from statistical physics that guides our probabilistic combinatorial proof. This is joint work with Coja-Oghlan, Hahn-Klimroth, Lee, Mueller and Rolvien.