A New Upper Bound for 7-Universal Tournaments

arXiv:2610.06891 · cs.DM, math.CO · Submitted 2026-09-24 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "A New Upper Bound for 7-Universal Tournaments".

Jane: Here's the gist of the paper. We give an explicit tournament on 14 vertices containing every 7-vertex tournament as an induced subtournament, and verify this property by exhaustive computation <ref:2610.06891#pg2>.

Tom: This improves the previously known upper bound of 15.

Jane: Together with the known lower bound, it follows that the minimum order of a 7-universal tournament is either 13 or 14.

Tom: The Main Result The central finding of this work is the construction and verification of a specific graph that serves as a host for all possible seven-vertex tournaments <ref:2610.06891#pg3>.

Paper summary: Tom: So we're looking at this paper called "A New Upper Bound for seven-Universal Tournaments" and the authors are saying they built a specific tournament with fourteen vertices that can contain every possible seven-vertex tournament as a smaller structure <ref:2610.06891#pg1,A New Upper Bound for 7-Universal Tournaments>.

Jane: That sounds intense, Tom. What’s the main point they’re making about this construction?

Tom: Well, essentially, they provide an explicit example of a fourteen vertex tournament that is seven-universal by checking every single one exhaustively. They found this improves on a previous upper bound which was fifteen vertices > <ref:2610.06891#pg1>#pg2.

Lu: So the core claim is that they can construct something on fourteen vertices that hosts all possible seven-vertex tournaments, and they verified it by checking all of them using a specific code based on the adjacency matrix entries, which is a really thorough way to prove it > <ref:2610.06891#pg3>#.

Meng: Exhaustive computation sounds like a lot of work. Does this mean we can actually figure out the absolute minimum size for these things?

Jane: It does. They combine this construction with a known lower bound from Zhang and Szeider, which says you need at least thirteen vertices, so they conclude that the minimum order for a seven-universal tournament must be either thirteen or fourteen > <ref:2610.06891#pg3>#.

Tom: Exactly. So the main result here is that they've established an upper bound of fourteen, and when you put that against the lower bound of thirteen, it forces the answer to be one of those two numbers.

Lalam: From my perspective, this paper confirms a specific configuration T14 is indeed seven-universal because their computation showed every possible code for all twenty-two one hundred nine thousand seven hundred fifty two labelled tournaments on seven vertices was covered > <ref:2610.06891#pg3>#.

Jane: That level of detail is what makes it solid. But beyond just finding the upper bound, what does this mean for how we think about these universal structures in general?

Lu: It shows that for this specific problem, the boundary between thirteen and fourteen is very tight, which constrains the possibilities significantly > <ref:2610.06891#pg3>#.

Meng: If we were trying to deploy a system based on one of these tournaments, knowing the size is either thirteen or fourteen gives us a very clear scale for what we need to build. It's not just some abstract limit anymore.

Tom: Right. So, before we wrap up, the paper by Verma and Szeider on "A New Upper Bound for seven-Universal Tournaments" essentially proves that the minimum order t of seven-universal tournaments is restricted to thirteen or fourteen > <ref:2610.06891#pg1>#pg2 <ref:2610.06891#pg1,A New Upper Bound for 7-Universal Tournaments>.

Jane: And it does this through a concrete construction on fourteen vertices and a full check against every possible seven-vertex tournament > <ref:2610.06891#pg3>#.

Lu: This work confirms that the upper bound for t of seven-universal tournaments is at most fourteen, which is an improvement over the previous bound of fifteen > <ref:2610.06891#pg1>#pg2.

Meng: So, what's next on our list? We've covered the summary and the conclusion; are there any other immediate implications we should look at regarding how this affects real-world applications?

Tom: For now, that’s it. The main thing is that we know exactly where to look for these structures—either thirteen or fourteen vertices—when searching for universal tournaments > <ref:2610.06891#pg3>#.

Conclusion: Tom: So we've seen the hard work on this paper, "A New Upper Bound for seven-Universal Tournaments," and now we need to talk about what that actually means for us beyond just the numbers.

Jane: It boils down to the authors building a specific fourteen vertex tournament that can hold every single possible seven vertex tournament as a piece inside it.

Tom: Right, so they’ve proven that fourteen is an upper limit for how big these universal structures need to be for seven tournaments. It improves on what was there before, which was fifteen vertices.

Jane: And when you put this new upper bound together with the lower bound from previous work, which said you need at least thirteen vertices, it really locks the minimum size down to either thirteen or fourteen.

Tom: Exactly. So the main conclusion is that we've narrowed down the possible order of these seven universal tournaments to just those two specific numbers.

Jane: It means for anyone trying to build something based on this concept, you only really have two options for your starting point, thirteen or fourteen vertices.

Tom: It’s a clear constraint on what we need to search for when looking at these mathematical objects.

Jane: And knowing that the exact number is still unresolved leaves us wondering which of those two values is the actual minimum size in reality. (Sound of traffic fades out)

Yale University

cs.DM, math.CO

Submitted: 2026-09-24

Updated: 2026-10-30

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 82/100

The gist: We give an explicit tournament on 14 vertices containing every 7-vertex tournament as an induced subtournament, and verify this property by exhaustive computation <ref:2610.06891#pg2>.

Key concepts

7-universal tournament
A graph (tournament) is called '7-universal' if it contains every possible way to arrange seven vertices in a competition (a 7-vertex tournament) as a smaller, induced structure within itself. The goal of the paper is to find the smallest such graph.
Induced Subtournament
An induced subtournament is formed by selecting a subset of vertices from the larger tournament and considering only the edges between those selected vertices. The property being tested is whether every possible 7-vertex tournament can be found this way inside the main 14-vertex graph.
Exhaustive Labelled Coverage
This verification method involves checking every single possible arrangement of seven labeled vertices within the 14-vertex tournament. This is done by enumerating ordered tuples of distinct vertices and using a code based on adjacency matrix entries to determine if the resulting subgraph matches one of the 2,097,152 potential tournaments.
Automorphism Group
The automorphism group of a graph is the set of all symmetries (relabelings) that leave the graph looking exactly the same. The paper uses this concept to classify all possible 7-element subsets into distinct isomorphism classes, helping confirm that their representations cover all required labelled tournaments.

Terminology

Summary

We give an explicit tournament on 14 vertices containing every 7-vertex tournament as an induced subtournament, and verify this property by exhaustive computation <ref:2610. p. 006891#pg2>. This improves the previously known upper bound of 15. p. 0 Together with the known lower bound, it follows that the minimum order of a 7-universal tournament is either 13 or 14. p. 0

The Main Result

The central finding of this work is the construction and verification of a specific graph that serves as a host for all possible seven-vertex tournaments <ref:2610.06891#pg3>. Theorem 1 states that there exists a 7-universal tournament on 14 vertices. p. 0 This result establishes the upper bound for the minimum order, showing that t(7) is at most 14. p. 0

Verification Method

The universality of the constructed tournament T14 is verified through two primary methods.

(a) Exhaustive labelled coverage:

The authors check all 2 21 = 2,097,152 possible labelled tournaments on the fixed label set of seven vertices by enumerating ordered tuples of distinct vertices from T14. They define a code c(v) based on the adjacency matrix entries to specify the resulting tournament. p. 1

(b) Verification up to isomorphism:

The paper also classifies the 7-element subsets of vertices into 456 distinct isomorphism classes, and by computing the orders of their automorphism groups, they confirm that a representative set H accounts for all labelled tournaments on seven vertices.

Bounding t(7)

The paper synthesizes prior results to narrow down the possible minimum order for a 7-universal tournament.

(a) Lower Bound:

Zhang and Szeider previously established a lower bound excluding 7-universal tournaments on twelve vertices. This implies that t(7) must be at least 13.

(b) Upper Bound Improvement:

The explicit construction on 14 vertices proves that the upper bound is at most 14, improving the previous bound of 15.

Conclusion

The exhaustive computation confirms that T14 is indeed 7-universal. Therefore, the minimum order t(7) is constrained to be either 13 or 14. p. 0 This result leaves the exact value of t(7) unresolved. p. 2

References

[2] John W. Moon. Topics on Tournaments, Holt, Rinehart and Winston, New York, 1968

[3] Stefan Szeider. SAT modulo symmetries: A survey, In Proceedings of the 10th International Workshop on Satisfiability Checking and Symbolic Computation (SC-Square 2025), volume 4116 of CEUR Workshop Proceedings, pages 1–11, 2025

[4] Tianwei Zhang and Stefan Szeider. Searching for smallest universal graphs and tournaments with SAT, In Roland H. p. 2 C. Yap, editor, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023), volume 280 of Leibniz International Proceedings in Informatics (LIPIcs), pages 39:1–39:20. p. 2 Schloss Dagstuhl–LeibnizZentrum für Informatik, 2023

[1] Noga Alon.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Enhanced Tournament Structure for Constraint Satisfaction Problems: The explicit 7-universal tournament on 14 vertices provides a structured host graph capable of containing every possible 7-vertex tournament as an induced subtournament. This can be used to model complex relational constraints in AI systems where the underlying logic requires testing all possible relative ordering combinations among a small set of interacting components.

  2. Improved Subtournament Generation and Verification: The method described in Section 3, using the function c(v) to generate codes for labelled tournaments, allows an AI system to systematically generate and verify all 2097152 possible labelled seven-vertex tournament configurations within a given host structure. This capability is useful for exhaustive search algorithms in problems like scheduling or resource allocation where every possible local ordering permutation must be validated.

  3. Refined Isomorphism Classification for Substructure Recognition: The classification of subtournaments into 456 distinct isomorphism classes with associated automorphism group orders provides a method for robustly recognizing and identifying specific relational patterns within larger graphs. An AI system can use these invariants to quickly classify the local structure of an input graph, allowing it to detect specific, known substructures efficiently.

Related papers