Research · Papers · Exact answers in open problems · MF-192
Verified structural obstructions for universal tournaments
No 9-host for TT_6 and 12 6-tournaments; no 11-host for TT_7, QR_7, and 7 rare 7-tournaments (DRAT verified)
Published 2026-09-06
For everyone
Plain summary
In a tournament, every pair of players has a match with a winner and a loser. A universal tournament is a host network big enough to contain every possible matchup pattern among a fixed number of players.
We show that certain small groups of patterns cannot fit together inside a single host network, backed by computer-verified certificates. Specifically, the transitive tournament TT_6 together with 12 named 6-player tournaments cannot share any 9-player host. Similarly, 9 highly symmetric tournaments on 7 players cannot share any 11-player host.
For the 11-player case, a simple head count already rules out fitting all 456 possible 7-player tournaments, since an 11-player host has only 330 seven-player subgraphs. The point here is structural: you do not need all 456 patterns to trigger a contradiction. Just these 9 specific patterns make an 11-player host impossible.
Result
Let t(k) denote the least order of a k-universal tournament.
(i) The transitive tournament TT_6 together with 12 specific 6-vertex tournaments has no common 9-vertex host tournament.
(ii) The transitive tournament TT_7 together with the eight rarest 7-vertex tournaments—namely the Paley tournament QR_7 with automorphism group order |Aut| = 21, the regular tournament with |Aut| = 7, three tournaments with |Aut| = 9, and three tournaments with |Aut| = 5—has no common 11-vertex host tournament.
Setting and definitions
A tournament T = (V, E) is an orientation of a complete graph. An induced sub-tournament on subset S ⊆ V(H) is isomorphic to T if a bijection preserves edge orientations. A host H embeds T when T is isomorphic to an induced sub-tournament of H. A tournament H is a common host for a family F if H embeds every member of F.
A tournament is k-universal if it embeds every k-vertex tournament. The parameter t(k) is the minimum vertex count of a k-universal tournament.
TT_k denotes the transitive tournament on k vertices, QR_7 denotes the 7-vertex Paley tournament, and |Aut| denotes the order of the automorphism group.
Method
The non-existence of common host tournaments was formulated as Boolean satisfiability problems and proved unsatisfiable using certified SAT solvers.
- For the 6-vertex family on 9-vertex hosts, the encoding produced 732 variables and 17,367 clauses. drat-trim verified unsatisfiability (
s VERIFIED) in 2.3 seconds. An independent second encoder re-derived and verified the result in 2.6 seconds. - For the 7-vertex family on 11-vertex hosts, the encoding produced 747 variables and 23,658 clauses. drat-trim verified unsatisfiability (
s VERIFIED) in 71 to 92 seconds across two independent encodings.
Execution receipts are recorded in lanes/tournaments-t7/BANK-CANDIDATES.md (candidates T7-02 and T7-03) and VERIFY.md, with verification environments in frontier/t7/ and frontier/t7-verify/.
Discussion
The bound t(7) > 11 follows directly from counting: an 11-vertex host tournament contains at most C(11,7) = 330 induced sub-tournaments of order 7, strictly fewer than the 456 non-isomorphic 7-vertex tournaments.
Zhang and Szeider (CP 2023) stated that "an obvious lower bound is 11" (though min{x : C(x,7) >= 456} yields 12) and evaluated n = 11 across four split SAT instances.
The contribution of entry MF-192 is the identification of exact structural obstructions rather than a numerical bound on t(7). Counting arguments cannot determine whether small sub-families embed jointly. The certified unsatisfiability proofs establish that 9 specific 7-vertex tournaments (and TT_6 together with 12 named 6-vertex tournaments) generate an irreconcilable structural conflict, preventing them from sharing an 11-vertex (or 9-vertex) host.
For everyone — the takeaway
What this means
Counting arguments show a host tournament is too small when it lacks enough total subgraphs to hold every target pattern. But counting cannot explain why specific patterns clash with one another.
These results pinpoint exact structural bottlenecks. Nine highly symmetric 7-player tournaments conflict so sharply that no 11-player tournament can hold them all at once. Machine-checked proofs confirm that these geometric clashes block universal embeddings independently of pure counting constraints.
Attribution and prior art
Prior art: Zhang and Szeider (CP 2023) stated a lower bound of 11 and resolved the case n = 11 using four separate SAT instances. Sources: Zhang, Szeider 2023 (CP 2023)
Register references
- Entry: MF-192
- Prior art: Zhang and Szeider, CP 2023
- Receipts:
lanes/tournaments-t7/BANK-CANDIDATES.md(T7-02, T7-03),VERIFY.md - Environments:
frontier/t7/,frontier/t7-verify/
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 (16 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-06An independent verification confirmed the per-pattern symmetry break is sound, matching brute-force results across 29 (k, n) cells with 0 failures, including k = 6, n = 10 (56/56 classes) and k = 5, n = 8 (12/12). On the n = 11 core, runtime dropped from 82.3 s to 0.40 s (a 207x speedup).