Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
osu1194991095.pdf (507.78 KB)
ETD Abstract Container
Abstract Header
On the likely number of stable marriages
Author Info
Lennon, Craig
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=osu1194991095
Abstract Details
Year and Degree
2007, Doctor of Philosophy, Ohio State University, Mathematics.
Abstract
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
n
1/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.
Committee
Boris Pittel (Advisor)
Pages
133 p.
Subject Headings
Mathematics
Keywords
Stable marriage
;
Probability
;
Combinatorics
Recommended Citations
Refworks
EndNote
RIS
Mendeley
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)
Abstract Footer
Document number:
osu1194991095
Download Count:
1,044
Copyright Info
© 2007, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.