Towards Optimal Degree Distributions for Left-Perfect Matchings in Random Bipartite Graphs

摘要

Consider a random bipartite multigraph G with n left nodes and m a parts per thousand yen na parts per thousand yen2 right nodes. Each left node x has d (x) a parts per thousand yen1 random right neighbors. The average left degree Delta is fixed, Delta a parts per thousand yen2. We ask whether for the probability that G has a left-perfect matching it is advantageous not to fix d (x) for each left node x but rather choose it at random according to some (cleverly chosen) distribution. We show the following, provided that the degrees of the left nodes are independent: If Delta is an integer, then it is optimal to use a fixed degree of Delta for all left nodes. If Delta is non-integral, then an optimal degree-distribution has the property that each left node x has two possible degrees, aOES Delta aOE < and aOE Delta aOE parts per thousand, with probability p (x) and 1-p (x) , respectively, where p (x) is from the closed interval [0,1] and the average over all p (x) equals aOE Delta aOE parts per thousand a'Delta. Furthermore, if c=n/m and Delta > 2 are constant, then each distribution of the left degrees that meets the conditions above determines the same threshold c (au)(Delta) that has the following property as n goes to infinity: If c < c (au)(Delta) then asymptotically almost surely there exists a left-perfect matching. If c > c (au)(Delta) then asymptotically almost surely there exists no left-perfect matching. The threshold c (au)(Delta) is the same as the known threshold for offline k-ary cuckoo hashing for integral or non-integral k=Delta.