Research · Papers · Exact answers in open problems · ML-090
Search wall for the smallest 7-universal tournament at order 13
13 ≤ t(7) ≤ 15; n = 13 undecided under SAT and lazy pattern-core CEGAR which exceeds 1800 s timeout at 32 enforced patterns
Published 2026-09-06
For everyone
Plain summary
A tournament is a round-robin competition where every pair of participants plays a directed match. A tournament is 7-universal if it contains every possible 7-participant tournament as a sub-tournament. There are 456 non-isomorphic 7-participant tournament patterns. Prior work by Zhang and Szeider showed that the smallest 7-universal tournament, denoted t(7), has between 13 and 15 vertices.
Whether a 13-vertex 7-universal tournament exists is still unknown. Automated SAT solvers and iterative search strategies hit a runtime wall. An incremental method that adds missing patterns one batch at a time exceeds its 1800-second limit after enforcing only 32 of the 456 patterns. Linear programming packing relaxations also fail because of an averaging collapse.
Result
The minimum order t(7) for a 7-universal tournament satisfies 13 ≤ t(7) ≤ 15. The decision problem at n = 13 is open. Monolithic SAT encodings and lazy pattern-core CEGAR loops both exceed the 1800 s timeout threshold once 32 patterns are enforced.
Setting and definitions
Let t(k) denote the minimum order n of a tournament H such that every k-vertex tournament T embeds as an induced subtournament of H. At k = 7, there are 456 non-isomorphic tournament patterns.
The monolithic SAT formulation for n = 13 contains 41,652 variables and 1,870,668 clauses covering all 456 target patterns. The lazy pattern-core CEGAR loop queries a SAT solver for a candidate host tournament satisfying a subset of rare pattern constraints, checks the candidate for missing patterns, and feeds violating patterns back into the solver as clauses. Evaluated baselines include SMS dynamic lex-leader symmetry breaking and CaDiCaL on the TT_7 + row-sort formulation.
Method
The n = 13 instance was tested under two SAT configurations:
- Direct monolithic solving: The complete 456-pattern formula (41,652 variables, 1,870,668 clauses) was run under CaDiCaL on the TT_7 + row-sort encoding and under SMS with dynamic lex-leader symmetry breaking. Neither solver decided the instance within 1800 s.
- Lazy pattern-core CEGAR: Patterns were ordered by rarity and enforced incrementally. While n = 11 resolved in 120 s (C(11,7) = 330 < 456), the inner SAT phase for n = 13 scaled exponentially: 1.0 s for 8 patterns, 5.8 s for 16 patterns, 193 s for 24 patterns, 1592 s for 32 patterns, and timed out at >1800 s thereafter. This scaling matches the known-UNSAT instance at n = 12.
Pattern-side symmetry breaking across four independent lineages accelerated core subroutines: runtimes dropped from 80.3 s to 0.31 s on the flagship core (~260x), reached a 272x speedup under a stabiliser chain, decided two 1800 s timeouts in 16 s and 55 s, and solved 11 amalgam cubes in 0.66 s combined (compared to the 80 s lane baseline and 3085 s published benchmark).
Artifacts are recorded in box logs at frontier/t7/, status.json, and lane log lanes/tournaments-t7/WALL.md.
Discussion
Zhang and Szeider (CP 2023) established 13 ≤ t(7) ≤ 15. Order n = 13 is the open lower bound.
The lazy pattern-core approach fails because the inner SAT phase scales exponentially long before covering the 456 required patterns. Because the runtime trajectory at n = 13 mirrors the known-UNSAT case at n = 12, solver thrashing on dense sub-pattern constraints drives the bottleneck rather than host tournament capacity.
Linear programming packing relaxations over rare patterns collapse under an averaging argument and provide no pruning power. While pattern-side symmetry breaking delivers two orders of magnitude in speedup across isolated components and amalgam cubes, deciding n = 13 remains unresolved.
For everyone — the takeaway
What this means
Testing whether a 13-node tournament can contain all 456 possible 7-node tournament matchups exceeds current solver limits. Vertex counting rules out 11 nodes, and earlier work proved 12 nodes cannot work either.
Adding missing patterns in batches times out after just 32 patterns. Linear programming shortcuts also provide no search reduction. While symmetry techniques accelerate isolated subproblems by ~260x, determining the exact value of t(7) between 13 and 15 remains open.
Attribution and prior art
Prior art: The bounds 13 <= t(7) <= 15 were established by Zhang and Szeider (CP 2023). Sources: Zhang, Szeider 2023 (CP 2023)
Register references
- ML-090
- Zhang and Szeider, CP 2023
- Box run logs and status file:
frontier/t7/status.json - Lane documentation:
lanes/tournaments-t7/WALL.md
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 2 of 2 receipt files bundled (4 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-06
- 2026-09-06Published on this site.
- 2026-09-06A new method (MF-192 addendum) certifies t(7) > 12 in about 1,389 s of solver time, superseding the published 2,002 CPU-days (MF-197) and completing the n = 12 verification. Search efforts now move to n = 13 using 15 amalgam cubes alongside MF-198 to eliminate candidate configurations.
- 2026-09-06The 20-pattern obstruction for 12-vertex hosts (MF-197) does not hold at n = 13 due to 15 explicit counter-witnesses, leaving t(7) at n = 13 open. Preregistered symmetric probes confirmed predictions, though the Z_3 probe timed out at 3,600 s and remains unknown under MF-198's Burnside bound.
- 2026-09-06Cube splitting, not automorphism breaking, overcomes the scaling wall at n = 12 and n = 13. While uncubed runs timed out at 7,200 s, 14 amalgam cubes decided the 20-pattern case in 1,395 s (MF-197) and took just 0.4-25 s per cube at n = 13.