Existence of a perfect matching in a random (\(1+e^{-1}\))-out bipartite graph
type: Item
instance of: scholarly article
title: Existence of a perfect matching in a random (\(1+e^{-1}\))-out bipartite graph
zbMATH Open document ID: 1026.05091
DOI: 10.1016/S0095-8956(03)00024-8
author: Michal Karonski
author: Boris Pittel
published in: Journal of Combinatorial Theory. Series B
publication date: 2003-08-25T00:00:00Z
review text: A random \(n\) by \(n\) bipartite graph \(B_n\) is constructed as follows: first, each vertex is made incident with an edge directed towards some vertex in the other partite set; next, each vertex of in-degree zero is made incident with a second edge directed towards some vertex in the other partite set. The selections are made uniformly and independently at random at each stage. Finally, each directed edge is replaced by the corresponding undirected edge and 2-cycles are replaced by single edges. The authors show, among other things, that the graph \(B_n\) has a perfect matching with probability \(1- O(n^{-1/2})\).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 1970672
zbMATH Keywords: random graphs
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: Maximum matchings in a class of random graphs
cites work: On Perfect Matchings and Hamilton Cycles in Sums of Random Trees
cites work: Average Case Analysis of a Heuristic for the Assignment Problem
cites work: Matching theory
cites work: Q5680148
cites work: Q4039989
cites work: The random bipartite nearest neighbor graphs
cites work: Matchings in superpositions of (n, n)‐bipartite trees
cites work: Matchings in random regular bipartite digraphs
description: scientific article; zbMATH DE number 1970672