{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T11:29:41Z","timestamp":1767007781506},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2009,5,1]],"date-time":"2009-05-01T00:00:00Z","timestamp":1241136000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2009,5]]},"abstract":"<jats:p>An instance of a size-<jats:italic>n<\/jats:italic> stable marriage problem involves <jats:italic>n<\/jats:italic> men and <jats:italic>n<\/jats:italic> women, each individually ranking all members of opposite sex in order of preference as a potential marriage partner. A complete matching, a set of <jats:italic>n<\/jats:italic> 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 (<jats:italic>n<\/jats:italic>!)<jats:sup>2<jats:italic>n<\/jats:italic><\/jats:sup> possible instances. The second author had proved that the expected number of stable marriages is of order <jats:italic>n<\/jats:italic>ln<jats:italic>n<\/jats:italic>, while its likely value is of order <jats:italic>n<\/jats:italic><jats:sup>1\/2\u2212<jats:italic>o<\/jats:italic>(1)<\/jats:sup> at least. In this paper the second moment of that number is shown to be of order (<jats:italic>n<\/jats:italic>ln<jats:italic>n<\/jats:italic>)<jats:sup>2<\/jats:sup>. The combination of the two moment estimates implies that the fraction of problem instances with roughly <jats:italic>cn<\/jats:italic>ln<jats:italic>n<\/jats:italic> solutions is at least 0.84. Whether this fraction is asymptotic to 1 remains an open question.<\/jats:p>","DOI":"10.1017\/s0963548308009607","type":"journal-article","created":{"date-parts":[[2008,12,4]],"date-time":"2008-12-04T05:21:12Z","timestamp":1228368072000},"page":"371-421","source":"Crossref","is-referenced-by-count":7,"title":["On the Likely Number of Solutions for the Stable Marriage Problem"],"prefix":"10.1017","volume":"18","author":[{"given":"CRAIG","family":"LENNON","sequence":"first","affiliation":[]},{"given":"BORIS","family":"PITTEL","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2009,5,1]]},"reference":[{"key":"S0963548308009607_ref8","unstructured":"[8] Knuth D. E. (1988) Personal communication."},{"key":"S0963548308009607_ref11","first-page":"486","article-title":"The stable marriage problem","volume":"14","author":"McVitie","year":"1971","journal-title":"Comm. Assoc. Comput. Mach."},{"key":"S0963548308009607_ref6","doi-asserted-by":"publisher","DOI":"10.1137\/0215048"},{"key":"S0963548308009607_ref10","unstructured":"[10] Lennon C. (2007) On the likely number of stable marriages. PhD dissertation, The Ohio State University, available at www.ohiolink.edu."},{"key":"S0963548308009607_ref3","volume-title":"An Introduction to Probability Theory and its Applications","author":"Feller","year":"1971"},{"key":"S0963548308009607_ref1","volume-title":"Probability and Measure","author":"Billingsley","year":"1995"},{"key":"S0963548308009607_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010102"},{"key":"S0963548308009607_ref16","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989126"},{"key":"S0963548308009607_ref7","volume-title":"Stable Marriage and its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms","author":"Knuth","year":"1976"},{"key":"S0963548308009607_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050307"},{"key":"S0963548308009607_ref2","volume-title":"Probability: Theory and Examples","author":"Durrett","year":"2005"},{"key":"S0963548308009607_ref13","doi-asserted-by":"publisher","DOI":"10.1137\/0402048"},{"key":"S0963548308009607_ref5","volume-title":"The Stable Marriage Problem: Structure and Algorithms","author":"Gusfield","year":"1989"},{"key":"S0963548308009607_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000481"},{"key":"S0963548308009607_ref12","first-page":"1","article-title":"Random stable matchings","volume":"10","author":"Mertens","year":"2005","journal-title":"J. Statist. Mech. Theory Exp."},{"key":"S0963548308009607_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01932966"},{"key":"S0963548308009607_ref4","doi-asserted-by":"publisher","DOI":"10.2307\/2312726"},{"key":"S0963548308009607_ref15","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005708"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548308009607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,6]],"date-time":"2019-04-06T15:37:49Z","timestamp":1554565069000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548308009607\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["S0963548308009607"],"URL":"https:\/\/doi.org\/10.1017\/s0963548308009607","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5]]}}}