2009/10/29 by Alan Frieze, Frieze, Alan, Páll Melsted +1 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.0910.5535
openalex publication_date 2009/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the the following question in Random Graphs. We are given two disjoint sets L,R with |L|=n=αm 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 four. We also establish a precise threshold for when Phase 1 of the Karp-Sipser Greedy matching algorithm suffices to compute a maximum matching whp.