Date
Tue, 06 Nov 2018
14:30
Location
L6
Speaker
Michael Simkin
Organisation
Hebrew University of Jerusalem

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.
 

Please contact us with feedback and comments about this page. Last updated on 04 Apr 2022 15:24.