Maximum Matchings in Random Bipartite Graphs and the Space Utilization of Cuckoo Hashtables

Alan Frieze, Páll Melsted

We study the the following question in Random Graphs. We are given two disjoint sets $L,R$ with $|L|=n=\alpha m$ and $|R|=m$. We construct a random graph $G$ by allowing each $x\in L$ to…