ACO The ACO Seminar (2018–2019)

October 11, 3:30pm, Wean 8220
Michael Simkin, Hebrew University of Jerusalem
Perfect matchings in random subgraphs of regular bipartite graphs


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=\Omega(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

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.

Back to the ACO home page