%0 Journal Article
%T Stable husbands
%A Donald E. Knuth
%A Rajeev Motwani
%A Boris Pittel
%J Mathematics
%D 1990
%I arXiv
%X Suppose $n$ boys and $n$ girls rank each other at random. We show that any particular girl has at least $({1\over 2}-\epsilon) \ln n$ and at most $(1+\epsilon)\ln n$ different husbands in the set of all Gale/Shapley stable matchings defined by these rankings, with probability approaching 1 as $n \to \infty$, if $\epsilon$ is any positive constant. The proof emphasizes general methods that appear to be useful for the analysis of many other combinatorial algorithms.
%U http://arxiv.org/abs/math/9201303v1