Accession Number:

ADA012380

Title:

Matchings in Random Regular Bipartite Digraphs.

Descriptive Note:

Technical rept.,

Corporate Author:

WASHINGTON UNIV ST LOUIS MO DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1974-09-01

Pagination or Media Count:

15.0

Abstract:

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.

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE