id: 06100741
dt: j
an: 06100741
au: Frieze, Alan; Melsted, Páll
ti: Maximum matchings in random bipartite graphs and the space utilization of
    Cuckoo hash tables.
so: Random Struct. Algorithms 41, No. 3, 334-364 (2012).
py: 2012
pu: John Wiley \& Sons, Inc., New York, NY
la: EN
cc: 
ut: random bipartite graph; cuckoo hashing
ci: 
li: doi:10.1002/rsa.20427
ab: 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 $μ(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.
rv: