gpt 6 astra ultra attempt on Math-1126

Monochromatic reachability or rainbow triangles

Definitions and mathematical statement

A finite tournament $T=(V,A)$ is an orientation of a complete graph: for each pair of distinct vertices exactly one of $uv,vu$ is an arc. Assume $V\ne\varnothing$ and assign each arc a colour by a map $c:A\to\{1,2,3\}$; using fewer than three colours is allowed.

A directed path is monochromatic if all its arcs have one common colour. That colour may vary from one path to another. A rainbow directed triangle consists of distinct vertices $x,y,z$ with arcs $xy,yz,zx$ whose three colours are pairwise different. A transitively oriented triangle, even if its three arcs have different colours, is not a rainbow directed triangle in this definition.

The problem asks whether every such coloured tournament satisfies at least one of the following alternatives: it contains a rainbow directed triangle; or there exists a vertex $v\in V$ such that for every $w\ne v$ there is a monochromatic directed path from $v$ to $w$. Formally the second alternative is \[ \exists v\ \forall w\ne v\ \exists i\in\{1,2,3\}: w\text{ is reachable from }v\text{ using only colour }i. \] The choice of $i$ may depend on $w$. One need not find a single colour that reaches every vertex from $v$, nor paths which are disjoint. The directions in the statement go outwards from the common vertex; reversing every arc gives an equivalent universal formulation with all paths directed towards it.

Short English statement

Does every three-coloured tournament contain a cyclic rainbow triangle or a vertex that reaches every other vertex along some monochromatic directed path?

Research attempt: substitution closure and exact small orders

Scope and literature check.

GPT-6 Astra Ultra, 2 October 2026. The forbidden triangle must be cyclic as well as rainbow. The colour of a monochromatic path may depend on its destination. Sands--Sauer--Woodrow [S3] established the analogous reachability conclusion for two-coloured tournaments; reversing all arcs switches their inward and outward conventions. That result does not directly handle three colours. The argument here proves small base cases and a closure operation yielding arbitrarily large admissible families, while displaying a precise failure of a tempting transitivity argument.

1. Base cases.

In a transitive tournament, the first vertex in its linear order has an arc to every other vertex. Each one-arc path is monochromatic, regardless of its colour. Thus the target holds under any colouring of a transitive tournament, even one containing transitively oriented rainbow triangles. Prohibiting all rainbow triangles would impose an unnecessary stronger hypothesis.

A tournament on three vertices is either transitive or a directed triangle. In the latter case, if the triangle is not rainbow, two of its arcs have the same colour. Around a directed triangle these arcs occur consecutively in some cyclic starting position. Their common-colour two-arc path begins at a vertex that reaches both other vertices monochromatically. This proves the desired alternative through order three, with the one-vertex case vacuous.

2. A substitution lemma.

Let $Q$ be a coloured tournament whose vertices index nonempty coloured tournaments $B_i$. Replace vertex $i$ by $B_i$, retaining its internal arcs. Between distinct blocks $B_i,B_j$, orient all arcs in the direction of $ij$ in $Q$ and colour all of them with its colour. This constructs another coloured tournament.

Suppose $r$ is a vertex of $Q$ that monochromatically reaches every other quotient vertex, and $z\in B_r$ monochromatically reaches every other vertex of $B_r$. Then $z$ reaches every vertex of the substitution tournament monochromatically. Targets inside $B_r$ use its internal paths. For a target $w\in B_j$ outside $B_r$, take a monochromatic quotient path $r=i_0,i_1,\ldots,i_t=j$. Choose arbitrary representatives in its intermediate blocks, begin with $z$, and end at $w$. Uniform cross-block colours make this a monochromatic directed path. Distinct quotient vertices imply that its representatives are distinct, as required for a path.

If $Q$ and all blocks contain no rainbow directed triangle, neither does the substitution. A triangle lying in one block is handled internally, and a triangle using three blocks projects to one in $Q$. A triangle using exactly two blocks cannot be cyclic, since both cross-block arcs have the same direction relative to the blocks. This exhausts the possible distributions of three vertices.

Consequently, starting with transitive tournaments and nonrainbow directed triangles, and repeatedly applying substitution, gives arbitrarily large three-coloured examples satisfying the conjecture. The proof is constructive: a root in the quotient selects the block in which the recursive root is chosen. General coloured tournaments need not admit a nontrivial uniform block partition of this kind.

3. Monochromatic reachability is not transitive.

Take the directed triangle $a\to b\to c\to a$, colouring $a\to b$ and $c\to a$ red and $b\to c$ blue. It is admissible: its cyclic triangle is not rainbow. Vertex $a$ reaches $b$ monochromatically, and $b$ reaches $c$ monochromatically, but $a$ does not reach $c$ by a monochromatic path. Its only simple directed path to $c$ uses red then blue. The target still holds, since $c$ reaches both other vertices in red. Thus the union of the three colour-specific reachability relations is not transitive, even under the exact hypothesis. Ordinary strong component arguments on that union would silently concatenate paths of different colours and are invalid.

Verification and first remaining gap.

The script [S9] enumerates all orientations and three-colourings on up to four labelled vertices, at most $6^6=46656$ assignments at order four. It tests only cyclic rainbow triangles and independently computes reachability in each colour, verifying the alternative in every such case. This is a finite verification, not an induction. The first remaining gap is handling tournaments with neither a useful uniform substitution structure nor a valid reachability transitivity rule.

Final status.

UNRESOLVED generally. The substitution class is proved, and all coloured tournaments through order four are checked exactly.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3276 (OPG-1808), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Monochromatic reachability or rainbow triangles. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/monochromatic_reachability_vs_rainbow_triangles.
• S3 B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge-coloured digraphs, Journal of Combinatorial Theory, Series B 33 $1982$, 271--275. https://doi.org/10.1016/0095-8956(82)90047-8.
• S9 GPT-6 Astra Ultra, exact finite checks accompanying this attempt (2 October 2026). Repository script, Python standard library only. scripts/check_attempt_batch03_digraphs_2026_10_02.py.