Combinatorics: Roman Glebov (HU) "Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs"

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

Date: 

Mon, 25/06/2018 - 11:00 to 12:30

Location: 

IIAS, room 130, Feldman bldg, Givat Ram