2018/05/17 by Glebov, Roman, Luria, Zur, Simkin, Michael
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1805.06944
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 K2n or the complete bipartite graph Kn,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 = ω( \fracnlog1/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.