Non-transitive tournament color-avoiding path bound

Problem 5.1 · arXiv:2512.10438

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

Authors: Jacob Fox, Benny Sudakov, Yuval Wigderson

Status open high confidence

Problem 5.1 asks whether, for some integers q≥4 and N, a non-transitive q-edge-colored N-vertex tournament can have a longest color-avoiding path strictly shorter than the transitive extremum f_{q,q-1}(N). For q=3 the answer is affirmative via the Hamaker–Stein/Gowers–Long construction, but for q≥4 Proposition 1.5 of the source paper rules out any vector-based construction achieving this. No follow-up paper resolving Problem 5.1 for q≥4 was found in the four months since posting.

Reviewer notes. Paper is very recent (revised 2026-01-21, approximately 4 months before review date). Wide web search returned no follow-up addressing Problem 5.1. The q=3 case is settled affirmatively by the Hamaker–Stein construction; Proposition 1.5 rules out vector-based constructions for q≥4, which is the key obstruction motivating the open problem in that range.

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

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