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
    0 references
    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
    0 references

    Identifiers