Research · Papers · Exact answers in open problems · MF-197
Machine-checked lower bound t(7) > 12 via fourteen amalgam cubes
t(7) > 12; no 12-vertex tournament is 7-universal (all 14 amalgam cubes UNSAT, drat-trim VERIFIED)
Published 2026-09-06
For everyone
Plain summary
A tournament is a round-robin contest where every pair of players plays once and there are no ties. A tournament is 7-universal if every possible 7-player tournament pattern appears inside it. The smallest tournament size that guarantees all 7-player patterns is called t(7). This work confirms that 12 players are not enough, so t(7) > 12.
No 12-player tournament can simultaneously contain even 20 specific 7-player sub-tournaments. By fixing two rigid 7-player tournaments and classifying all 14 ways they can overlap, the search splits into 14 subproblems called amalgam cubes. A SAT solver proved that none of these 14 cases can be completed into a valid tournament, and an independent checker verified the resulting mathematical proofs in roughly 1,389 seconds across four CPU slots. Zhang and Szeider first proved t(7) > 12 in 2023 using about 2,002 CPU-days. While the numerical bound is not new and the novelty of the amalgam-cube approach remains unverified, this certified proof finishes thousands of times faster.
Result
t(7) > 12. No 12-vertex tournament embeds the Paley tournament QR_7, the regular tournament R_7 with |Aut| = 7, and the eighteen further 7-vertex patterns enforced during lazy iteration. Consequently, no 12-vertex tournament is 7-universal. All 14 amalgam cubes at n = 12 are unsatisfiable, certified by drat-trim with output s VERIFIED.
Setting and definitions
Let t(k) denote the minimum vertex count n such that every tournament on k vertices embeds as an induced subtournament of some n-vertex tournament. There are 456 non-isomorphic tournaments on 7 vertices.
Let QR_7 denote the 7-vertex Paley tournament, and let R_7 denote the 7-vertex regular tournament with |Aut(R_7)| = 7. The maximum common subtournament shared by QR_7 and R_7 has order 4.
An amalgam cube at order n is a propositional formula fixing an embedding of QR_7 and R_7 onto subsets of {1, ..., n} that intersect on r vertices, chosen up to the action of Aut(QR_7) x Aut(R_7), conjoined with pattern-absence clauses and per-pattern automorphism symmetry-breaking constraints.
Method
Fix QR_7 and R_7 in an ambient 12-vertex tournament. Classifying their intersections on r vertices modulo Aut(QR_7) x Aut(R_7) yields:
- r = 1: 1 orbit
- r = 2: 3 orbits
- r = 3: 7 orbits
- r = 4: 4 orbits
- r >= 5: 0 orbits, bounded by the maximum common subtournament order of 4.
Summing across r ∈ {1, 2, 3, 4} produces 14 amalgam cubes at n = 12 (compared to 11 at n = 11 and 15 at n = 13).
Each cube incorporates the eighteen further 7-vertex patterns selected in the campaign's second lazy iteration alongside the per-pattern automorphism symmetry breaks detailed in the MF-192 addendum.
The verification harness generates CNF instances independently via venc3.py and vetamal.py, matching the target CNFs bit for bit (sha prefixes 9bce8c87... and 7143f97a...). All 14 cubes evaluate to UNSAT. Proof checking with drat-trim outputs s VERIFIED. Total execution required roughly 1,389 solver seconds across four slots plus certificate checking. Both potential outcomes were preregistered in tests/amalgam-n12/PREREG.md.
Discussion
At n = 12, counting arguments fail: C(12,7) = 792 exceeds the 456 target non-isomorphic 7-vertex tournaments.
Zhang and Szeider (CP 2023) established t(7) > 12 by splitting across 16,384 sub-instances over approximately 2,002 CPU-days. The 14-cube amalgam formulation discharges the order in 1,389 multi-core solver seconds.
The amalgam-cube decomposition and pattern-side symmetry breaking do not appear in Zhang and Szeider (CP 2023), the December 2025 SMS survey, or the CP 2026 cubing paper; their formal novelty remains UNVERIFIED. The exact value of t(7) remains open, with the next cell at n = 13 spanning 15 amalgam cubes.
For everyone — the takeaway
What this means
Determining whether small networks can simultaneously embed all possible sub-patterns on small vertex sets is a fundamental question in combinatorics. Finding the threshold for 7-player tournaments has long been computationally intractable because the space of directed graphs grows exponentially.
This result confirms that 12 vertices cannot contain every 7-vertex tournament. While first proved through massive distributed computation, the 14-cube amalgam reduction settles the bound in under half an hour on a standard machine and supplies an independently checked certificate.
Attribution and prior art
Prior art: This value matches Zhang-Szeider (CP 2023), though the novelty of the amalgam-cube method and pattern-side symmetry breaking remains unverified against that paper, the Dec-2025 SMS survey, and the CP 2026 cubing paper. The open cell n = 13 (15 cubes) is the next instance. Sources: Zhang, Szeider 2023 (CP 2023)
Register references
- Register entry: MF-197
- Verification receipt: lanes/tournaments-t7/verify-invent/VERDICTS.md
- Preregistration log: tests/amalgam-n12/PREREG.md
- Pipeline scripts: vetamal.py, venc3.py
- Verification environment: box frontier/t7-vet/
- Prior art: Zhang and Szeider, CP 2023; SMS survey (Dec 2025); CP 2026 cubing paper
- Cross-reference: MF-192 addendum (per-pattern automorphism break)
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 4 of 4 receipt files bundled (10 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.