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