Existence of a perfect matching in a random (\(1+e^{-1}\))-out bipartite graph (Q1405096)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Existence of a perfect matching in a random (\(1+e^{-1}\))-out bipartite graph |
scientific article |
Statements
Existence of a perfect matching in a random (\(1+e^{-1}\))-out bipartite graph (English)
0 references
25 August 2003
0 references
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})\).
0 references
random graphs
0 references