Large domination number forces Sᵢ subtournament

Problem 3 · arXiv:1702.01607

arXiv Problem high confidence— first stated 2017-03-15

Authors: Ararat Harutyunyan, Tien-Nam Le, Stéphan Thomassé, Hehui Wu

Status open high confidence

Problem 3 from arXiv:1702.01607 — that for every $i \geq 1$ there exists $f(i)$ such that every tournament with dominating number at least $f(i)$ contains an isomorphic copy of $S_i$ — remains open for all $i \geq 4$. Aboulker, Aubian, Charbit, and Lopes (arXiv:2310.04265, 2023) embed the conjecture (as their Conjecture 5.2) into a three-statement implication chain involving a proven theorem and an intermediate Conjecture 5.3, and observe that showing every $S_k$ is a rebel would imply Conjecture 5.3. A separate 2023 survey (arXiv:2306.02364) dedicates Section 9 to the two conjectures of Harutyunyan et al. and Section 13 to excluding $S_t$, treating the full statement as open.

Cited literature (1)

partial Clique number of tournaments (2023)

Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Raul Lopes · arXiv preprint · arXiv:2310.04265

Introduces the notion of tournament clique number, places Problem 3 as Conjecture 5.2, introduces an intermediate Conjecture 5.3, proves an implication chain among the three statements, and notes that showing every $S_k$ is a rebel would imply Conjecture 5.3.

Reviewer notes. All three internal references are duplicates pointing to arXiv:2310.04265. An additional survey arXiv:2306.02364 ('Some results and problems on tournament structure') was located via search and partially verified via HTML fetch: it contains Section 9 titled 'Two conjectures of Harutyunyan et al.' and Section 13 titled 'Excluding S_t', and cites Harutyunyan-Le-Thomasse-Wu as reference [9]; however, the authors of 2306.02364 could not be confirmed before the 5-call cap was reached, so it is omitted from since_posted. No paper resolving Problem 3 for i >= 4 was found in the indexed literature.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. For every integer $i \geq 1$, there exists $f(i)$ such that every tournament $T$ with dominating number at least $f(i)$ contains an isomorphic copy of $S_i$.

Context

The tournaments $S_i$ are defined recursively: $S_1$ is a single vertex, and for $i > 1$, $S_i$ is the tournament on $2^i - 1$ vertices obtained by blowing up two vertices of an oriented triangle into two copies of $S_{i-1}$; one can check $\vec{\chi}(S_i) \geq i$. The problem is trivial for $i \leq 2$, verified for $i = 3$ in [7], and open for all $i \geq 4$.

Notes. PDF source — math notation may be partially garbled; recursive definition of $S_i$ reconstructed from surrounding text.

Source paper

Coloring tournaments: from local to global
Ararat Harutyunyan, Tien-Nam Le, Stéphan Thomassé, Hehui Wu · 2017-03-15
https://arxiv.org/abs/1702.01607 PDF source