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

Abstract

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 choose $d$ random neighbours in $R$. The question discussed is as to the size $\mu (G)$ of the largest matching in $G$. When considered in the context of Cuckoo Hashing, one key question is as to when is $\mu (G)=n$ whp? We answer this question exactly when $d$ is at least four. We also establish a precise threshold for when Phase 1 of the Karp-Sipser Greedy matching algorithm suffices to compute a maximum matching whp.

References in corpus (2)

• Finite size scaling for the core of large random hypergraphs
• Sharp Load Thresholds for Cuckoo Hashing

Cited by in corpus (5)

• Tight Thresholds for Cuckoo Hashing via XORSAT
• Orientability thresholds for random hypergraphs
• Matchings on infinite graphs
• On the Insertion Time of Cuckoo Hashing
• Towards Optimal Degree-distributions for Left-perfect Matchings in Random Bipartite Graphs