• 2018 Jun 25

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

11:00am to 12:30pm

## Location:

IIAS, Eilat hall, Feldman bldg, Givat Ram
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)$.