Non-transitive tournament color-avoiding path bound

AX_tournament_color_avoiding_path_non_transitive

Source: arXiv:2512.10438 — Color-avoiding directed paths in tournaments

Problem 5.1 · arXiv:2512.10438

arXiv Problem high confidence— first stated 2026-01-21

Authors: Jacob Fox, Benny Sudakov, Yuval Wigderson

Status ai-proved high confidence

Yes: for q=6 and N=9 there is a non-transitive coloring with longest color-avoiding path on 7 vertices, whereas f_{6,5}(9)=8.

Auto-reviewed 2026-08-31 with gpt-5.6-sol.

AI-generated write-up ai-proved

Open the PDF write-up

This is a model-generated research artifact, not a peer-reviewed publication or a formally verified proof.

Problem. For some integers $q\geqslant 4$ and $N$, does there exist a non-transitive $q$-edge-colored $N$-vertex tournament whose longest color-avoiding path has strictly fewer than $f_{q,q-1}(N)$ vertices?

Context

For $q\geqslant 4$, Proposition 1.5 shows $F_{q,q-1}(n)=G_{q,q-1}(n)$, meaning the largest $(q-1)$-comparable set is always a $(q-1)$-increasing sequence and hence corresponds to a transitive tournament. Problem 5.1 asks whether a non-transitive coloring can do strictly worse than the transitive extremum. The answer is affirmative for $q=3$ via the Hamaker–Stein construction, but Proposition 1.5 rules out any vector-based construction for $q\geqslant 4$, leaving the problem open in that range.

Source paper

Color-avoiding directed paths in tournaments
Jacob Fox, Benny Sudakov, Yuval Wigderson · 2026-01-21
https://arxiv.org/abs/2512.10438