Search ETDs:
On the likely number of stable marriages
Lennon, Craig

2007, Doctor of Philosophy, Ohio State University, Mathematics.
An instance of a size n - stable marriage problem involves n men and n women, each individually ranking all members of opposite sex in order of preference as a potential marriage partner. A complete matching, a set of n marriages, is called stable if no unmatched man and woman prefer each other to their partners in the matching. It is known that, for every instance of marriage partner preferences, there exists at least one stable matching, and that there are instances with exponentially many stable matchings. Our focus is on a random instance chosen uniformly from among all (n!)2n possible instances. Boris Pittel had proved that the expected number of stable marriages is of order n ln(n), while its likely value is of order n1/2-o(1) at least. Here it is shown that the second order moment of that number is of order (n ln n)2. The combination of the two moment estimates implies that the fraction of problem instances with roughly c n ln(n) solutions is 0.84, at least.
Boris Pittel (Advisor)
133 p.

Recommended Citations

Hide/Show APA Citation

Lennon, C. (2007). On the likely number of stable marriages. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Lennon, Craig. "On the likely number of stable marriages." Electronic Thesis or Dissertation. Ohio State University, 2007. OhioLINK Electronic Theses and Dissertations Center. 25 Sep 2017.

Hide/Show Chicago Citation

Lennon, Craig "On the likely number of stable marriages." Electronic Thesis or Dissertation. Ohio State University, 2007. https://etd.ohiolink.edu/

Files

osu1194991095.pdf (507.78 KB) View|Download