10.1184/R1/6478367.v1
Alan Frieze
Alan
Frieze
Pall Melsted
Pall
Melsted
Maximum Matchings in Random Bipartite Graphs and the Space Utilization of Cuckoo Hash Tables
Carnegie Mellon University
2012
random bipartite graph
Cuckoo Hashing
2012-02-02 00:00:00
Journal contribution
https://kilthub.cmu.edu/articles/journal_contribution/Maximum_Matchings_in_Random_Bipartite_Graphs_and_the_Space_Utilization_of_Cuckoo_Hash_Tables/6478367
<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>