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

journal contribution

posted on 02.02.2012 by Alan Frieze, Pall Melsted#### journal contribution

Any type of content formally published in an academic journal, usually following a peer-review process.

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