Combinatorics

  • 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)$.