Stable husbands

Donald E. Knuth, Rajeev Motwani, Boris Pittel

Suppose $n$ boys and $n$ girls rank each other at random. We show that any particular girl has at least $(\frac{1}{2}-\epsilon )\ln n$ and at most $(1+\epsilon )\ln n$ different husbands in the se…