Paper detail

Towards Optimal Degree-distributions for Left-perfect Matchings in Random Bipartite Graphs

Consider a random bipartite multigraph $G$ with $n$ left nodes and $m \geq n \geq 2$ right nodes. Each left node $x$ has $d_x \geq 1$ random right neighbors. The average left degree $Δ$ is fixed, $Δ\geq 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, $\floorΔ$ and $\ceilΔ$, 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 $\ceilΔ-Δ$. Furthermore, if $n=c\cdot m$ and $Δ>2$ is 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 there exists a left-perfect matching with high probability. If $c>c^*(Δ)$ then there exists no left-perfect matching with high probability. The threshold $c^*(Δ)$ is the same as the known threshold for offline $k$-ary cuckoo hashing for integral or non-integral $k=Δ$.