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

Consider a random bipartite multigraph G with n left nodes and m ≥ n≥2 right nodes. Each left node x has d _x ≥1 random right neighbors. The average left degree Δ is fixed, Δ≥2. 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 Δ is an integer, then it is optimal to use a fixed degree of Δ for all left nodes. If Δ is non-integral, then an optimal degree-distribution has the property that each left node x has two possible degrees, ⌊Δ⌋ and ⌈Δ⌉, 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 ⌈Δ⌉−Δ. Furthermore, if c=n/m and Δ>2 are constant, then each distribution of the left degrees that meets the conditions above determines the same threshold c ^∗(Δ) that has the following property as n goes to infinity: If c < c ^∗(Δ) then asymptotically almost surely there exists a left-perfect matching. If c>c ^∗(Δ) then asymptotically almost surely there exists no left-perfect matching. The threshold c ^∗(Δ) is the same as the known threshold for offline k-ary cuckoo hashing for integral or non-integral k=Δ.