Search

Consider a random bipartite multigraph G with n left nodes and m ≥ n≥2 right nodes. Each left node x has d≥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 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 and 1− p, respectively, where p is from the closed interval [0,1] and the average over all p 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=Δ. [ABSTRACT FROM AUTHOR]