OFFSET
1,2
COMMENTS
Finding a(n) (denoted f(n) in the literature) is a research problem posed by Knuth in 1976 and reiterated by Gusfield and Irving in 1989.
a(5)=16 was found by Eilers using a MiniZinc constraint satisfaction model, showing previous lower bound of Eilers reported by Thurber to be exact.
A357271 gives lower bounds for a(n) reported by Thurber, previously known to be exact up to n=4, which is not to be confused with A069156 which gives looser lower bounds for n > 11.
Thurber proved a(n) to be strictly increasing.
There are 176130 reduced instances of order 5 with 16 stable matchings, and 498320 reduced instances with 15 stable matchings, compared with A351430 for order 4, and compared with [2840,957,91] for order 3.
The total number of reduced instances for order n is A351409(n), which is 214990848000000000 for order 5, so about one in 1.22*10^12 such instances are maximal.
The maximum number of stable matchings for order 5, where the men's (or women's, respectively) ranking table is a latin square, is 14, with 300 such reduced instances, making order 5 the first order not containing any maximal instances where the men's ranking table is a Latin square.
REFERENCES
C. Converse, Lower bounds for the maximum number of stable pairings for the general marriage problem based on the latin marriage problem, Ph. D. Thesis, Claremont Graduate School, Claremont, CA (1992).
D. R. Eilers, "The Maximum Number of Stable Matchings in the Stable Marriage Problem of Order 5 is 16". In preparation.
D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989, (Open Problem #1).
LINKS
A. T. Benjamin, C. Converse, and H. A. Krieger, Note. How do I marry thee? Let me count the ways, Discrete Appl. Math. 59 (1995) 285-292.
Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, Sequences of the Stable Matching Problem, arXiv:2201.00645 [math.HO], 2021, [Section 5, Distribution for the number of stable matchings].
D. E. Knuth, Mariages Stables, Presses Univ. de Montréal, 1976 (Research Problem #5).
E. G. Thurber, Concerning the maximum number of stable matchings in the stable marriage problem, Discrete Math., 248 (2002), 195-219.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Dan Eilers, Sep 21 2022
STATUS
approved