Exact bounds for the stochastic upward matching problem
Wansoo T. Rhee, Michel Talagrand · Transactions of the American Mathematical Society · 1988
We draw at random independently and according to the uniform distribution two sets of n n points of the unit square. We consider a maximum matching of points of the first set with points of the second set with the restriction that a point can be matched only with a point located at its upper right. Then with probability close to one, the number of unmatched points is of order n 1 / 2 ( log n ) 3 / 4 {n^{1/2}}{(\log n)^{3/4}} .