CS Paper Radar

A New Upper Bound for 7-Universal Tournaments

Harshit Verma

cs.DM math.CO ·submitted 2026-09-24 21:27 UTC · v2
theory

Abstract

A tournament is $k$-universal if it contains every tournament on $k$ vertices as a subtournament. We give a 7-universal tournament on 14 vertices, improving the upper bound of 15 due to Zhang and Szeider. Together with their lower bound, it follows that the smallest 7-universal tournament has 13 or 14 vertices.

Closest papers

Nearest neighbours by meaning across the whole index.

Tournaments not inducible by five voters

cs.DM ·2026-09-12 ·Leonid Chindelevitch, Ararat Harutyunyan
theory similarity 0.73
Abstract · 31 pages, 4 figures; v2: upper bound improved to $N(5) \leq 22$ (v1: $\leq 23$), refuting v1's conjecture $N(5) = 23$. Companion paper: arXi…

How many members must a committee have before its pairwise majorities can express any collective preference? With enough voters every pattern of pairwise majorities, or tournament, can arise, but a committee of $k$ voters produces only some; for odd $k$, let $N(k)$ be the least number of alternatives on which some tournament arises from no $k$ voters. Only $N(3) = 8$ is known; for five voters our companion paper gave $12 \le N(5) \le 38$ and the first explicit example of moderate size, on 43 vertices. We show $13 \le N(5) \le 22$. The upper bound comes from nine tournaments on 22 vertices that five voters cannot produce: eight one-vertex deletions of doubly regular tournaments on 23 vertices, including every deletion of one of them, and one arc reversal. The Paley tournament on 23 vertices, which Bachmeier et al. (2019) left open after six weeks of SAT solving, is beyond five voters, and so is every other doubly regular tournament on 23 vertices. The lower bound comes from an analysis of all tournaments on 12 vertices. Both doubly regular tournaments on 19 vertices, the Paley tournament and one other, arise from five voters, but not with unit margin, that is, not with every majority carried by three votes to two. The method is a search that places one alternative at a time and exploits the tournament's symmetries; four of the negative results are certified by machine-checkable proofs, and all results are reproducible from a public repository.

0.21

Clique Number of Tournaments II

cs.DM math.CO ·2026-09-07 ·Guillaume Aubian, Samuel Coulomb
theory similarity 0.70
Abstract

The directed clique number $\vecω(T)$ of a tournament $T$ is the minimum, over all orderings of the vertices of $T$, of the clique number of the graph whose edges are the arcs that point backward with respect to the ordering. In this paper, we prove that, for every integer $k \geq 3$, deciding whether $\vecω(T) \leq k$ is NP-complete. This answers a question of Nguyen, Scott, and Seymour, and contrasts with the classical undirected setting, where deciding whether $ω(G) \leq k$ is polynomial-time solvable for every fixed integer $k$. On the other hand, we give a polynomial-time algorithm distinguishing tournaments with $\vecω(T) \leq 2$ from those with $\vecω(T) > 100$. We also study the tournament analogue of the Gyárfás--Sumner conjecture. We construct new $\vecχ$-bounding tournaments and thereby prove a conjecture of Aboulker, Aubian, Charbit, and Lopes stating that every class of tournaments with bounded twin-width is $\vecχ$-bounded. We then exhibit new tournaments that are not $\vecχ$-bounding, disproving another conjecture of Aboulker, Aubian, Charbit, and Lopes, as well as two conjectures of Kim. Finally, we present infinite families of 3-$\vecω$-critical and 4-$\vecω$-critical tournaments.

0.06

Crossing tournaments are polynomially $\vecχ$-bounded

cs.DM math.CO ·2026-08-10 ·Lila Crew, Xinyue Fan, Hidde Koerts, Benjamin Moore, Sophie Spirkl
similarity 0.69
Abstract

Given a tournament $T$, Aboulker, Aubian, Charbit, and Lopes (2023) defined its clique number $\vecω(T)$ as the minimum clique number of a backedge graph of $T$, and raised the question: Which classes of tournaments are polynomially $\vecχ$-bounded? Aboulker, Duron, Jacob, Kimbrough, Thomassé, and this work's authors (2026) showed that this holds for classes of tournaments whose arc sets may be written as the union of a bounded number of comparability digraphs. What about classes of tournaments that do not admit such a decomposition? The crossing tournaments of Nguyen, Scott, and Seymour (2025) are an example of such a class, as shown in the aforementioned 2026 work; we show that nonetheless crossing tournaments are polynomially $\vecχ$-bounded by adapting a method of Davies and McCarty (2021) and Davies (2022). We additionally show that we cannot extend this result for crossing tournaments to tournaments with chordal graphs as backedge graphs.

0.04

Digraphs of Large Girth and Dichromatic Number in Tournaments with Large Dichromatic Number

cs.DM math.CO ·2026-09-18 ·Pierre Charbit, Samuel Coulomb
theory similarity 0.67
Abstract

In the 1960s, Erdős and Hajnal conjectured that every graph with sufficiently large chromatic number contains a subgraph of large girth (size of a smallest cycle) and large chromatic number. In this paper, we prove that every tournament with sufficiently large dichromatic number contains a subdigraph of large digirth (size of a smallest directed cycle) and large dichromatic number. We investigate the same statement when replacing digirth by girth (of the underlying graph). We show that it implies the conjecture of Erdős and Hajnal, and prove it for a particular family of tournaments.

0.07

Note on near-spanning balanced antidirected trees missing from regular tournaments

cs.DM math.CO ·2026-10-01 ·Gregory Gutin, Yiming Hao
similarity 0.67
Abstract · 6 pages

We construct near-spanning balanced antidirected trees that fail to embed in highly symmetric tournaments despite the conjectured semidegree condition being satisfied. More precisely, for every sufficiently large odd integer $n$, we exhibit a regular vertex-transitive tournament on $n$ vertices and a balanced antidirected caterpillar on $n-1$ vertices with maximum degree at most $(1+o(1))n/\log_2 n$ that is not contained in the tournament. The host satisfies the strict $k/2$ threshold in both the semidegree and pseudo-semidegree settings, where $k$ is the number of arcs of the target tree. Consequently, this gives counterexamples to the uniform sublinear-degree interpretations of Conjectures~6.8 and~7.6 in Stein's survey (2024). The order $n-1$ of the target is best possible under the strict semidegree hypothesis. We also give a six-vertex balanced antidirected double-star missing from the seven-vertex Paley tournament, and show that seven is the smallest host order for a pseudo-semidegree counterexample with this fixed double-star.

0.16

Directed Cut-Query Complexity of Finding a King

cs.CC math.CO ·2026-10-29 ·Ziad Ismaili Alaoui, Oded Lachish, Nikhil S. Mande
theory similarity 0.65
Abstract

A king in a tournament is a vertex from which every other vertex is reachable by a directed path of length at most two. We study the deterministic query complexity of finding a king when a query specifies a set of vertices and returns the number of edges directed from that set to its complement. We prove that this complexity is $Θ(n)$ for $n$-vertex tournaments. To show this, we first show that every correct deterministic algorithm in this model must output a maximum-outdegree vertex, even though a king need not have maximum outdegree. We then give an adversary whose answers, after too few queries, remain consistent with a tournament in which the algorithm's output does not have maximum outdegree.

0.34

FPT Isomorphism Test for $F$-Free Tournaments

cs.DS cs.DM ·2026-09-21 ·Daniel Neuen
similarity 0.65
Abstract · 17 pages

We show that isomorphism of $F$-free tournaments can be solved in FPT time $f(k) \cdot n^{O(1)}$, where $k$ denotes the size of $F$, and $n$ denotes the size of the input tournaments. Our result extends on a previous FPT isomorphism test for tournaments of bounded twin-width [Grohe, Neuen 2024], as well as XP isomorphism tests parameterized by the VC dimension or the chromatic number [Raßmann, Schweitzer 2026]. It also implies that every non-trivial hereditary class of tournaments admits a polynomial-time isomorphism test. Our algorithm builds on a novel combination of spectral, geometric, combinatorial and group-theoretic tools.

0.11

Isomorphism of tournaments with bounded VC dimension

cs.DS cs.DMmath.CO ·2026-08-14 ·Simon Raßmann, Pascal Schweitzer
similarity 0.64
Abstract

The tournament isomorphism problem is one of the two fundamental bottlenecks to designing better algorithms for the graph isomorphism problem. Though the problem has been investigated for more than five decades, compared to graphs, there are only very few results on the isomorphism problem of tournaments. For most classes of tournaments neither hardness nor polynomial-time solvability is known. Tournaments of bounded VC dimension are such a class for which no results are available, even though the VC dimension is arguably one of the most robust and central notions of combinatorial tameness. Resolving an open problem of Neuen and Grohe, we show that the isomorphism problem for tournaments of VC dimension $d$ can be decided in time $n^{O(d\log d)}$. Consequently, automorphism groups of tournaments of bounded VC dimension can be computed in polynomial time. To this end, we develop a new method to isomorphism-invariantly decompose tournaments. To facilitate recursion, we introduce the notion of a patched tournament and analyze bounded VC dimension in patched tournaments. We design a recursive algorithm that balances the size of the decomposed pieces against their number and makes use of the structure of near twins. In an orthogonal direction, it is known that a hereditary class of tournaments has unbounded VC dimension if and only if it contains all 2-colorable tournaments. As a second result, we show that also this class does not form an obstruction towards polynomial-time isomorphism testing and indeed show that isomorphism of tournaments of bounded chromatic number is polynomial-time decidable.

0.32