Random bipartite matching from empty-rectangle exclusion ($P(\text{no perfect matching})\le 3n^{2\lceil \sqrt{n}\rceil }(1-p{)}^{n/2}⟶0$)

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.