On constrained matchings, stable under random preferences

Colloquially, there are two groups, n men and n women, each man (woman) ranking women (men) as potential marriage partners. A complete matching is called stable if no unmatched pair prefer each other to their partners in the matching. If some pairs are not admissible, then such a matching may not exist, but a properly defined partial stable matching exists always, and all such matchings involve the same, equi-numerous, groups of men and women. Earlier we proved that, for the complete, random, preference lists, with high probability (whp) the total number of complete stable matchings is, roughly, of order n^1/2, at least. Here we consider the case that the preference lists are still complete, but a generic pair (man, woman) is admissible with probability p, independently of all other n²-1 pairs. It is shown that the expected number of complete stable matchings tends to 0 if, roughly, p² nn. We show that whp: (a) there exists a complete stable matching if p> (9/4) ² nn, (b) the number of unmatched men and women is bounded if p> ²nn, and (c) this number grows as a fractional power of n for p<² nn.