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

Martin Dietzfelbinger, Michael Rink

Consider a random bipartite multigraph $G$ with $n$ left nodes and $m\ge n\ge 2$ right nodes. Each left node $x$ has $d_x\ge 1$ random right neighbors. The average left degre…