Speaker: Roman Glebov (HU)
Title: Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs
Abstract:
Consider the random process in which the edges of a graph $G$ are
added one by one in a random order. A classical result states that if
$G$ is the complete graph $K_{2n}$ or the complete bipartite graph
$K_{n,n}$, then typically a perfect matching appears at the moment at
which the last isolated vertex disappears. We extend this result to
arbitrary $k$-regular bipartite graphs $G$ on $2n$ vertices for all
$k=\Omega(n)$.
Surprisingly, this is not the case for smaller values of $k$. We
construct sparse bipartite $k$-regular graphs in which the last
isolated vertex disappears long before a perfect matching appears.
Joint work with Zur Luria and Michael Simkin