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

<p>We study the the following question in Random Graphs. We are given two disjoint sets <em>L</em>,<em>R</em> with |<em>L</em>| = <em>n</em> and |<em>R</em>| = <em>m</em>. We construct a random graph <em>G</em> by allowing each <em>x</em>∈<em>L</em> to choose <em>d</em> random neighbours in <em>R</em>. The question discussed is as to the size μ(<em>G</em>) of the largest matching in <em>G</em>. When considered in the context of Cuckoo Hashing, one key question is as to when is μ(<em>G</em>) = <em>n</em> whp? We answer this question exactly when <em>d</em> is at least three.</p>