Matchings in Random Regular Bipartite Digraphs.
WASHINGTON UNIV ST LOUIS MO DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
Let G be a random directed bipartite graph with n nodes in each class and outward degree d at each node. The probability G contains a matching is shown to approach one for large n if d or 2, but to approach zero if d 1. This result complements and contrasts with a result of Erdos and Renyi which implies the probability of a matching does to zero if the number of arcs chosen at random without regard to regularity grows more slowly than n log n.
- Statistics and Probability