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.
展开▼
机译：我们在随机图中研究以下问题。给定两个不相交的集合L，R，| L |。 = n和| R | =米我们通过允许每个x∈L在R中选择d个随机邻居来构造随机图G。讨论的问题是关于G中最大匹配项的大小μ（G）。在杜鹃哈希中，一个关键问题是何时μ（G）= n whp？当d至少为3时，我们恰好回答了这个问题。
展开▼
