Determine f(6), the maximum number of stable matchings in a stable marriage instance of order 6 (Knuth 1976, Research Problem #5; Gusfield-Irving 1989, Open Problem #1)
Statement
For the stable marriage problem of order n (n men, n women, complete strict preference lists), let f(n) be the maximum, over all instances, of the number of distinct stable matchings that instance admits. Determine f(6) exactly: either exhibit an instance of order 6 with more than the best value stated in background and verify its stable-matching count exhaustively, or prove that value optimal by an exhaustive or certified search over order-6 instances.
Acceptance. FULLY RESOLVES: (a) an order-6 preference table whose exhaustively-verified stable-matching count strictly exceeds the best value stated in background, raising the lower bound; OR (b) a search that certifies the best value stated in background is optimal for n = 6, with the search's symmetry-reduction argument stated precisely enough to be re-run. Either way, ship the instance(s) and an enumeration script. ADVANCES: a verified exhaustive result over a clearly-delimited sub-family of order-6 instances (e.g. all instances within a bounded neighbourhood of the Thurber composition construction, or a fixed cyclic/dihedral symmetry class - NOT the Latin-square family, whose order-6 maximum is the already-recorded incumbent 48 (OEIS A351413), so exhausting it re-derives a known value rather than advancing the bound), with the family's size and the reduction argument stated; or an independently reproduced re-derivation of the known f(5) = 16 result as a validated engine, published as a negative/partial result if the order-6 search does not close. Machine-checkable in all cases: an instance plus a counting script.
Background
f(n) was posed by Knuth in 'Mariages Stables' (1976) as Research Problem #5 and reiterated by Gusfield and Irving, 'The Stable Marriage Problem: Structure and Algorithms' (MIT Press, 1989) as Open Problem #1. Exact values are known only for n <= 5: f(1..5) = 1, 2, 3, 10, 16 (OEIS A357269, keyword `more`). f(4) = 10 was settled by exhaustive computer search; f(5) = 16 was settled only recently by Dan Eilers using a MiniZinc constraint-satisfaction model, confirming that Thurber's composition-based lower bound was tight at n = 5. For n = 6 the best known lower bound is 48, from Thurber (2002, Appendix C) via composition of smaller instances, and it is CONJECTURED to be exact (the same conjecture is made for n = 8, 10, 12, 16) - but it is not proved. OEIS A357271 tracks these composition lower bounds. Thurber proved f is strictly increasing. Asymptotics are comparatively well understood and are NOT the target here: f(n) <= 3.55^n + O(1) (Palmer-Palvolgyi, arXiv:2011.00915) against a lower bound of roughly 2.28^n. Counting stable matchings of a given instance is #P-complete in general, but for a single instance of order 6 the rotation poset makes enumeration instant. Search trap: the Latin sub-family (preference tables that are Latin squares) is a natural symmetry reduction, correct at orders 1-4, but it cannot ESTABLISH f(6). At order 5 the Latin maximum is 9 while f(5) = 16, so the true maximum can lie outside the family; and at order 6 the Latin maximum is already recorded as 48 (OEIS A351413 = 1, 2, 3, 10, 9, 48, 61 - itself empirically derived and not independently verified), so a Latin-restricted order-6 search reproduces a known value rather than advancing the bound. It is therefore a legitimate independent-VERIFICATION target, not an attack on f(6). Attacker's tool: a CSP/SAT or ILP model over order-6 preference tables with rotation-poset and relabelling symmetry breaking, in the style of the Eilers order-5 model; verification of any exhibited instance is a millisecond-scale stable-matching enumeration that any reviewer can rerun.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | OEIS A357269 | website |
| REF-02 | OEIS A357271 | website |
| REF-03 | OEIS A351413 — max stable matchings over Latin-square instances (Latin maxima) | website |
| REF-04 | Knuth, Mariages Stables (Stanford) | website |
| REF-05 | DOI (published article) | doi |
| REF-06 | DOI (published article) | doi |
| REF-07 | arXiv:2201.00645 | arxiv |
| REF-08 | arXiv:2011.00915 | arxiv |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.