= Random bipartite matching from empty-rectangle exclusion
{title2=$P(\text{no perfect matching})\leq 3n^{2\lceil\sqrt n\rceil}(1-p)^{n/2}\longrightarrow0$}
In the equal-part random <bipartite graph> with fixed edge probability $0<p<1$, rule out empty rectangles of side $\lceil\sqrt n\rceil$ and vertices with at least $n-\lceil\sqrt n\rceil$ nonneighbors. A union bound gives the displayed asymptotic estimate. Small vertex sets satisfy Hall's condition by the degree bound; intermediate sets do so because their omitted-neighbor rectangle would contain a forbidden square; large sets meet every vertex in the other part. Thus <Hall's marriage theorem> gives a perfect matching asymptotically almost surely. This does not mean probability one at any finite size.
Back to article page
