Bounded-size ω→-witness subtournament

Question 5.9 · arXiv:2310.04265

arXiv Question high confidence— first stated 2023-10-06

Authors: Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Raul Lopes

Status disproved high confidence

Disproved by the arbitrarily large k-ω⃗-critical tournaments of Chen and Wang (Theorem 1.1, arXiv:2609.08658): for fixed k ≥ 3, no bound on witness size can hold at the unchanged threshold k.

Cited literature (2)

counterexample Cayley Tournaments Simultaneously Critical for the Clique and Dichromatic Numbers (2026)

Guantao Chen, Shengze Wang · arXiv preprint · arXiv:2609.08658

Theorem 1.1 supplies arbitrarily large k-ω⃗-critical tournaments for every k ≥ 3, refuting the bounded-witness question.
partial Characterizing Large Clique Number in Tournaments (2026)

Logan Crew, Xinyue Fan, Hidde Koerts, Benjamin Moore, Sophie Spirkl · arXiv preprint · arXiv:2602.09863

Corollary 7 proves bounded-size witnesses under the stronger hypothesis ω⃗(T) ≥ f(k), settling the weaker Conjecture 5.8, not the unchanged-threshold Question 5.9.

Reviewer notes. Corrected on 2026-09-10 following Samuel Coulomb's report; both cited results were checked in the full text. To derive the counterexample, fix k ≥ 3 and choose a k-ω⃗-critical T larger than any proposed bound ℓ(k). Every candidate witness A omits a vertex v, so ω⃗(T[A]) ≤ ω⃗(T - v) = k - 1 by monotonicity. This does not contradict the weaker threshold result in Corollary 7.

Auto-reviewed 2026-09-10 with codex (web search enabled).

Question. Is there a function $\ell$ such that, for every tournament $T$, if $\operatorname{\overrightarrow{\omega}}(T)\geq k$, then $T$ has a subtournament $A$ such that $|A|\leq\ell(k)$ and $\operatorname{\overrightarrow{\omega}}(A)\geq k$.

Context

This is a stronger form of Conjecture 5.8 in which the function $f$ is taken to be the identity. The authors could not disprove it, and note that Conjecture 5.10 (infinitely many $k$-$\operatorname{\overrightarrow{\omega}}$-critical tournaments) would answer it negatively.

Source paper

Clique number of tournaments
Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Raul Lopes · 2023-10-06
https://arxiv.org/abs/2310.04265