06100741

j

06100741 Frieze, Alan Melsted, P\'all Maximum matchings in random bipartite graphs and the space utilization of Cuckoo hash tables. Random Struct. Algorithms 41, No. 3, 334-364 (2012). 2012 John Wiley \& Sons, Inc., New York, NY EN random bipartite graph cuckoo hashing

doi:10.1002/rsa.20427

Summary: 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\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 three.