The classical theory of Erdős–Rényi random graphs is concerned primarily with random subgraphs of $K_n$ or $K_{n,n}$. Lately, there has been much interest in understanding random subgraphs of other graph families, such as regular graphs.

We study the following problem: Let $G$ be a $k$-regular bipartite graph with $2n$ vertices. Consider the random process where, beginning with $2n$ isolated vertices, $G$ is reconstructed by adding its edges one by one in a uniformly random order. An early result in the theory of random graphs states that if $G=K_{n,n}$, then with high probability a perfect matching appears at the same moment that the last isolated vertex disappears. We show that if $k = Ω(n)$, then this holds for any $k$-regular bipartite graph $G$. This improves on a result of Goel, Kapralov, and Khanna, who showed that with high probability a perfect matching appears after $O(n \log(n))$ edges have been added to the graph. On the other hand, if $k = o(n / (\log(n) \log (\log(n)))$, we construct a family of $k$-regular bipartite graphs in which isolated vertices disappear long before the appearance of perfect matchings.

Joint work with Roman Glebov and Zur Luria.