cp's OEIS Frontend

A351413 a(n) is the maximum number of stable matchings in the Latin Stable Marriage Problem of order n.

%I A351413 #17 Feb 28 2022 19:39:25
%S A351413 1,2,3,10,9,48,61
%N A351413 a(n) is the maximum number of stable matchings in the Latin Stable Marriage Problem of order n.
%C A351413 In the Latin Stable Marriage Problem of order n, the sum of a man and woman's rankings of each other is n+1. This implies that the men's and women's ranking tables are Latin squares. As a subproblem of the Stable Marriage Problem, Latin instances provide lower bounds for the maximum number of stable matchings in the general problem, such as A005154 and A065982. For sizes 1 to 4, Latin instances provide exact bounds; they are conjectured to provide exact bounds for sizes a power of 2; they provide the best lower bounds known for sizes 6, 10, 12, and 24, of 48, 1000, 6472, and 126112960, respectively.
%C A351413 The next term, a(8), is conjectured to be 268, consistent with A005154. The minimum number of stable matchings for Latin instances of order n is n, and is realized for the cyclic group of order n. The average number of stable matchings is 7 for n=4 (cf. A351430 showing an average of about 1.5 for the general problem), and benefits from avoidance of mutual first choices and more generally the lack of overlap between the men's and women's preferred matchings. The Latin squares of A005154 and A065982 can be interpreted as multiplication tables of groups, n-th powers of the cyclic group C2 and n-th dihedral groups, respectively.
%C A351413 The sequence decreases from a(4)=10 to a(5)=9, in contrast to the corresponding sequence for the general problem, which Thurber showed to be strictly increasing. This has motivated the study of less restrictive subproblems, such as pseudo-Latin squares (A069124, A069156), Latin x Latin instances (A344664, A344665, A343697), instances where participants have different first choices (A343475, A343694, A343695), or instances with unspecified/tied/template rankings (A284458 with only first choices specified).
%C A351413 The sequence is empirically derived, originally based on reduced Latin squares (A000315). There are fewer instances to try using RC-equivalent Latin squares (A123234) instead of reduced Latin squares.
%D A351413 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) [Examples are from 69-70].
%H A351413 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 A351413 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 [Sections 3.7 and 4.2].
%H A351413 J. S. Hwang, <a href="https://doi.org/10.1007/BFb0091807">Complete stable marriages and systems of I-M preferences</a>, In: McAvaney K.L. (eds) Combinatorial Mathematics VIII. Lecture Notes in Mathematics, vol 884. Springer, Berlin, Heidelberg (1981) 49-63.
%H A351413 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.
%e A351413 Maximal instance of order 2 with 2 stable matchings:
%e A351413   12
%e A351413   21
%e A351413 Maximal instance of order 3 with 3 stable matchings:
%e A351413   123
%e A351413   231
%e A351413   312
%e A351413 Maximal instance of order 4 with 10 stable matchings (group C2xC2):
%e A351413   1234
%e A351413   2143
%e A351413   3412
%e A351413   4321
%e A351413 Maximal instance of order 5 with 9 stable matchings:
%e A351413   12345
%e A351413   21453
%e A351413   34512
%e A351413   45231
%e A351413   53124
%e A351413 Maximal instance of order 6 with 48 stable matchings (Dihedral group):
%e A351413   123456
%e A351413   214365
%e A351413   365214
%e A351413   456123
%e A351413   541632
%e A351413   632541
%e A351413 Maximal instance of order 7 with 61 stable matchings:
%e A351413   1234567
%e A351413   2316745
%e A351413   3125476
%e A351413   4657312
%e A351413   5743621
%e A351413   6471253
%e A351413   7562134
%Y A351413 Cf. A005154 (powers of 2), A065982 (multiples of 2), A069156 (not necessarily Latin), A000315 (reduced Latin squares), A123234 (RC-equivalent Latin squares).
%K A351413 nonn,hard,more
%O A351413 1,2
%A A351413 _Dan Eilers_, Feb 10 2022