Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

On the likely number of stable marriages

Lennon, Craig

Abstract Details

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

Citations

  • Lennon, C. (2007). On the likely number of stable marriages [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1194991095

    APA Style (7th edition)

  • Lennon, Craig. On the likely number of stable marriages. 2007. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1194991095.

    MLA Style (8th edition)

  • Lennon, Craig. "On the likely number of stable marriages." Doctoral dissertation, Ohio State University, 2007. http://rave.ohiolink.edu/etdc/view?acc_num=osu1194991095

    Chicago Manual of Style (17th edition)