Scott–Seymour property for random tournaments

Conjecture 12 · arXiv:2305.15585

arXiv Conjecture high confidence— first stated 2023-12-04

Authors: António Girão, Kevin Hendrey, Freddie Illingworth, Florian Lehner, Lukas Michel, Michael Savery, Raphael Steiner

Status open high confidence

Conjecture 12 from arXiv:2305.15585 posits that the uniformly random tournament on $[N]$ witnesses the Scott–Seymour phenomenon with high probability: for every $k$ there exists $\chi$ such that whp every graph $G$ on $[N]$ with $\chi(G)\geq\chi$ contains a vertex $v$ whose out-neighborhood induces a subgraph of chromatic number at least $k$. The source paper disproves the deterministic Scott–Seymour conjecture using highly structured tournaments, and Conjecture 12 asserts that such structured adversarial examples cannot be replaced by a random tournament. No subsequent paper resolving or making partial progress on this specific conjecture was found in the indexed literature as of May 2026.

Reviewer notes. No follow-up found addressing Conjecture 12 specifically. The source paper itself was published in Journal of Combinatorial Theory, Series B, vol. 168 (2024), pp. 86–95. Web searches found no paper proving or disproving this random-tournament variant of the Scott–Seymour phenomenon. The conjecture is recent (≤2 years) and absence of follow-up is expected; status open with high confidence.

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

Conjecture. For every positive integer $k$, there exists a $\chi$ such that if $T$ is the uniformly random tournament on vertex set $[N]$, then with high probability (as $N\to\infty$), for every graph $G$ on $[N]$ with $\chi(G)\geqslant\chi$ there is a vertex $v\in[N]$ for which $G[N^{+}_{T}(v)]\geqslant k$.

Context

The counterexamples to Conjecture 1 use very structured tournaments; the authors conjecture that a random tournament cannot be used as such a counterexample, i.e., that the Scott–Seymour phenomenon holds with high probability for the random tournament.

Notes. The statement as extracted likely contains a typographical omission: '$G[N^{+}_{T}(v)]\geqslant k$' should read '$\chi(G[N^{+}_{T}(v)])\geqslant k$'.

Source paper

Chromatic number is not tournament-local
António Girão, Kevin Hendrey, Freddie Illingworth, Florian Lehner, Lukas Michel, Michael Savery, Raphael Steiner · 2023-12-04
https://arxiv.org/abs/2305.15585