gpt 6 astra ultra attempt on Math-1127

Decomposing an even tournament in directed paths.

Definitions and mathematical statement

Let $T=(V,A)$ be a finite tournament on an even number $n\ge2$ of vertices. A tournament has exactly one arc between each pair of distinct vertices. Write $d^+(v)$ and $d^-(v)$ for the outdegree and indegree of $v$, so $d^+(v)+d^-(v)=n-1$. Define its total positive excess by \[ \operatorname{ex}(T)=\sum_{v\in V}\max\{0,d^+(v)-d^-(v)\}. \] A directed path has distinct vertices and follows the arc directions. A path decomposition is a collection of nonempty directed paths whose arc sets partition $A$. Paths may share vertices, but each arc must occur exactly once.

The conjecture asks whether every even-order tournament has a path decomposition into exactly $\operatorname{ex}(T)$ paths. This is the smallest possible count suggested by endpoint balance. Indeed, at a vertex $v$, the number of paths starting there minus the number ending there equals $d^+(v)-d^-(v)$; summing the required starts gives the stated lower bound.

Evenness is essential to the formulation. In a regular tournament of odd order all excesses are zero although there are arcs to decompose. For even order every difference $d^+(v)-d^-(v)$ is odd, and the sum of all differences is zero, yielding $\operatorname{ex}(T)\ge n/2$. When each difference has absolute value one, the conjectured $n/2$ paths must each be Hamiltonian, because together they must cover $n(n-1)/2$ arcs and one path has at most $n-1$ arcs.

Short English statement

Can every even-order tournament be decomposed into the number of directed paths forced by its degree imbalances?

Research attempt: exact decompositions for acyclic tournaments

Scope and literature check.

GPT-6 Astra Ultra, 2 October 2026. Paths are simple and nonempty, and their arc sets must partition all arcs. Girão, Granet, Kühn, Lo and Osthus [S3] proved the conjecture for every sufficiently large even-order tournament. This important advance settles that range; it should not be paraphrased as a theorem for every finite order. The independent work below proves the acyclic subclass at all orders, explains the obstruction to naive local pairings, and connects the extremal excess case to Hamilton decompositions.

1. An exact path-count theorem for every acyclic digraph.

Let $D$ be any finite acyclic digraph. At each vertex arbitrarily pair $\min(d^-,d^+)$ incoming arcs with distinct outgoing arcs. Think of a paired outgoing arc as the successor of its paired incoming arc. Each arc has at most one successor and at most one predecessor, so the resulting components of arcs are directed chains or closed chains. A closed chain would project to a directed closed walk in $D$, which is impossible in an acyclic digraph.

Moreover a chain cannot repeat a vertex: the segment between two occurrences would again be a directed closed walk. Every component is consequently a simple directed path. The starts are exactly the outgoing arcs left unpaired at their tails. Their number is \[ \sum_{v\in V}\max\{0,d^+(v)-d^-(v)\} =\operatorname{ex}(D). \] All arcs occur once, proving an exact decomposition. Isolated vertices create no nonempty path and contribute zero to the count. This attains the usual endpoint lower bound, which follows by subtracting the number of paths ending at a vertex from the number starting there and summing all required positive differences.

For a transitive tournament of even order $2m$, number the vertices $0,\ldots,2m-1$ with arcs directed from smaller to larger indices. Its positive differences are $2m-1,2m-3,\ldots,1$, whose sum is $m^2$. The pairing construction therefore decomposes it into exactly $m^2$ paths, verifying the original target for every such tournament.

2. What the pairing proof loses when cycles are present.

On vertices $0,1,2,3$, take the cycle $0\to1\to2\to0$ and arcs from each of $0,1,2$ to $3$. Its excess is three. Pairing each incoming cycle arc to the next outgoing cycle arc leaves a closed triangle, together with three one-arc paths ending at $3$. The local balance condition has not produced a path decomposition with the required number of paths.

Re-pairing does work in this particular example: the paths \[ (0,1,2,3),\qquad(1,3),\qquad(2,0,3) \] partition all six arcs and number three. The example distinguishes failure of arbitrary local pairings from failure of the conjecture. More generally a pairing component can also project to an open trail revisiting a vertex; being a chain of distinct arcs does not by itself make it a simple path.

3. Why the least-excess case requires global structure.

Suppose every degree difference in an even tournament has absolute value one. Its excess is $n/2$. Any decomposition into $n/2$ paths must use only Hamilton paths, since their maximum total number of arcs is $(n/2)(n-1)$, exactly the number needing coverage.

Now start with a regular tournament $R$ on $2m+1$ vertices and delete one vertex $z$. In the remaining tournament, the former outneighbours of $z$ have excess $+1$, while its former inneighbours have excess $-1$. If a minimum decomposition into $m$ paths exists, every path is Hamiltonian and starts at a distinct positive vertex and ends at a distinct negative vertex. Append $z$ using the arcs from $z$ to the start and from the end back to $z$. This gives $m$ arc-disjoint Hamilton cycles covering every arc of $R$. The accounting proves that the present problem includes a Hamilton decomposition requirement in this extremal class; it cannot be reduced merely to finding one Hamilton path at a time.

Verification, gap and final status.

The script [S9] verifies the acyclic construction for transitive tournaments through order twenty and computes exact minimum path partitions for every labelled tournament on four vertices. It also checks the displayed obstruction and its repair. The first general gap is eliminating closed or vertex-repeating pairing components without increasing the number of starts. Full all-order target: UNRESOLVED here, with the sufficiently large range already proved in [S3].

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3277 (OPG-46237), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Decomposing an even tournament in directed paths.. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/decomposing_an_even_tournament_in_directed_paths.
• S3 António Girão, Bertille Granet, Daniela Kühn, Allan Lo and Deryk Osthus, Path decompositions of tournaments, Proceedings of the London Mathematical Society $2023$. https://arxiv.org/abs/2010.14158; https://doi.org/10.1112/plms.12480.
• 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.