A357269 - OEIS

%I #25 Nov 06 2022 08:35:08

%S 1,2,3,10,16

%N Maximum number of stable matchings in the stable marriage problem of order n.

%C 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.

%C 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.

%C 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.

%C Thurber proved a(n) to be strictly increasing.

%C 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.

%C 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.

%C 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.

%D 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 D. R. Eilers, "The Maximum Number of Stable Matchings in the Stable Marriage Problem of Order 5 is 16". In preparation.

%D D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989, (Open Problem #1).

%H A. T. Benjamin, C. Converse, and H. A. Krieger, <a href="https://doi.org/10.1016/0166-218X(95)80006-P">Note. How do I marry thee? Let me count the ways</a>, Discrete Appl. Math. 59 (1995) 285-292.

%H Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, <a href="https://arxiv.org/abs/2201.00645">Sequences of the Stable Matching Problem</a>, arXiv:2201.00645 [math.HO], 2021, [Section 5, Distribution for the number of stable matchings].

%H D. E. Knuth, <a href="https://www-cs-faculty.stanford.edu/~knuth/ms.html">Mariages Stables</a>, Presses Univ. de Montréal, 1976 (Research Problem #5).

%H E. G. Thurber, <a href="https://doi.org/10.1016/S0012-365X(01)00194-7">Concerning the maximum number of stable matchings in the stable marriage problem</a>, Discrete Math., 248 (2002), 195-219.

%Y Cf. A357271 and A069156 (lower bound of 16 for a(5)).

%Y Cf. A351430 (order 4).

%Y Cf. A351409 (total number of reduced instances).

%K nonn,more

%O 1,2

%A _Dan Eilers_, Sep 21 2022