Existence of a perfect matching in a random (\(1+e^{-1}\))-out bipartite graph (Q1405096)

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})\).