Premium
Perfect matchings in random subgraphs of regular bipartite graphs
Author(s) -
Glebov Roman,
Luria Zur,
Simkin Michael
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22650
Subject(s) - combinatorics , bipartite graph , mathematics , vertex (graph theory) , complete bipartite graph , strong perfect graph theorem , matching (statistics) , discrete mathematics , line graph , random regular graph , graph , 1 planar graph , statistics
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 2 nor 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 2 n vertices for all k = ω ( n log 1 / 3 n ) . Surprisingly, this is not the case for smaller values of k . Using a construction due to Goel, Kapralov, and Khanna, we show that there exist bipartite k ‐regular graphs in which the last isolated vertex disappears long before a perfect matching appears.