Sumner's Conjecture

Sumner’s Tournament Embedding Conjecture

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A tournament chooses exactly one orientation for each edge of a complete graph. An oriented tree is an arbitrary orientation of a finite undirected tree. For each $n\geq2$, ask whether every tournament on $2n-2$ vertices contains every oriented tree on $n$ vertices as an orientation-preserving subgraph; induced embedding is not required. [S1] [S2]

Statement recorded in the supplied source.

Does every $2n-2$-vertex tournament contain every n-vertex oriented tree? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Resolve the finite range not covered by the sufficiently-large-n theorem, or give a genuinely uniform proof of f(n)=2n-2. [S1]

Short English statement

Does every tournament on twice n minus two vertices contain every possible orientation of an n-vertex tree?

Research attempt

Uniform statement and known large-order theorem.

The target is every $n\ge2$ and every orientation of every $n$-vertex tree. The primary abstract of Kühn, Mycroft, and Osthus [E1] proves the conjecture for sufficiently large $n$. Ai and Lian's 2026 abstract [E2] gives the uniform upper bound $f(n)\le\lceil(18n-23)/7\rceil$. These assertions have different quantifiers and neither abstract by itself supplies the missing uniform sharp result. This attempt proves the sharp obstruction, two complete tree families, and the smallest orders directly.

The number $2n-2$ is necessary.

For $n\ge2$, put $m=2n-3$ and take vertices in ${\mathbb{Z}}/m{\mathbb{Z}}$. When $m>1$, orient the edge from $i$ to $j$ if $j-i\pmod m\in\{1,\ldots,n-2\}$. Exactly one of the two opposite nonzero differences is in this set, so this is a tournament, and every vertex has outdegree $n-2$. It contains no out-star with $n-1$ leaves, since the image of the centre would need outdegree at least $n-1$. At $n=2$ the one-vertex tournament supplies the same obstruction trivially. Thus any uniform unavoidable order satisfies \[ f(n)\ge2n-2. \] This establishes sharpness of the proposed constant if the upper bound is eventually proved. It does not establish that upper bound.

Both orientations of stars satisfy the exact bound.

In any tournament on $2n-2$ vertices, the sum of all outdegrees is $\binom{2n-2}{2}$. Their average is $(2n-3)/2=n-3/2$, so some integer outdegree is at least $n-1$. Choose that vertex for the centre and any $n-1$ of its outneighbours for the leaves. This embeds the out-star. Applying the same calculation to indegrees embeds the in-star. Edges between the leaves are irrelevant, since the embedding is not required to be induced. Ignoring that last convention would incorrectly rule out every nontrivial tree in a tournament.

Consistently directed paths require even fewer vertices.

Every finite tournament has a directed Hamiltonian path. Prove this by induction: take a directed path $v_1\to\cdots\to v_s$ through the old vertices and insert a new vertex $w$. If $w\to v_1$, insert it first. Otherwise find the first $i$ with $w\to v_i$; minimality implies $v_{i-1}\to w$, so insertion between $v_{i-1}$ and $v_i$ works. If no such $i$ exists, every $v_i\to w$, and appending $w$ works. Every consecutive edge retains the required orientation.

Taking any $n$-vertex subtournament and this path embeds the oriented tree whose edges all point along one path direction. This proof does not cover arbitrary alternating orientations of a path: a directed Hamiltonian path has one consistent orientation, and reversing selected edges is not an available operation on the tournament. The distinction matters when identifying the family actually proved.

All oriented trees of orders two and three.

At order two, any tournament with two vertices has one oriented edge, which embeds either labeling of the two-vertex oriented tree. At order three the underlying tree is a path with two edges. Its orientation is an in-star, an out-star, or a consistently directed path, up to relabeling. The preceding proofs therefore settle every orientation at $n=3$ in a four-vertex tournament, as required.

The executed check enumerates all $2^{\binom42}=64$ labeled tournaments on four vertices and all four edge orientations of the labeled path $0-1-2$. It tries all injective maps of its vertices into the tournament and verifies an embedding in each of the $256$ cases. The exhaustive check agrees with the symbolic classification; it is not used to extrapolate to larger trees.

The obstruction to the most immediate leaf induction.

Delete a leaf $u$ from a tree $T$ and suppose the remaining tree has been embedded. If $u$ is an out-leaf at its parent $v$, extension requires an unused outneighbour of the image of $v$; for an in-leaf it requires an unused inneighbour. The average-degree calculation above finds a suitable centre somewhere in the tournament, but the image of $v$ in an already fixed embedding need not be that vertex. It may have used all neighbours of the required orientation.

For a minimal illustration of this logical failure, a transitive three-vertex tournament has a sink with no outneighbour. An embedding of a one-vertex parent at that sink cannot be extended to an out-edge, although an out-edge certainly embeds elsewhere. Thus a failed greedy extension is not a counterexample, and counting the globally unused vertices alone does not repair it. A successful induction needs control of the possible parent images, or a rerouting theorem preserving the already embedded branches. No such uniform rerouting lemma is proved in this attempt.

Verification record and exact remaining gap.

The tournament enumeration is in checks_graphs.py and results_graphs.json under _Local/Erdos_problems/UnsolvedMath/attempt_audit_2026_10_01/number_theory/. The sharp lower bound holds for every $n$, and the sharp upper bound is proved here for the two star orientations and for $n\le3$, with an even stronger result for consistently directed paths. Arbitrary branching orientations and the full uniform finite range remain uncovered by these deductions. The large-order theorem is reported with its actual quantifier, not converted into an unperformed finite verification. Outcome: UNRESOLVED.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1424 (GRAPH-037), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Daniela Kuhn, Richard Mycroft, and Deryk Osthus, A proof of Sumner's universal tournament conjecture for large tournaments, Proceedings of the London Mathematical Society 102 $2011$, 731-766. https://arxiv.org/abs/1010.4430. Bibliographic information from the supplied record.

• S3 Jiangdong Ai and Xiaopan Lian, An improved finite bound for oriented trees in tournaments, arXiv:2608.11667 $2026$. https://arxiv.org/abs/2608.11667. Bibliographic information from the supplied record.

• E1 Daniela Kühn, Richard Mycroft, and Deryk Osthus, A proof of Sumner's universal tournament conjecture for large tournaments, arXiv:1010.4430; Proc. London Math. Soc. 102 $2011$, 731--766. https://arxiv.org/abs/1010.4430. Primary abstract inspected 1 October 2026.
• E2 Jiangdong Ai and Xiaopan Lian, An improved finite bound for oriented trees in tournaments, arXiv:2608.11667v1. https://arxiv.org/abs/2608.11667. Primary abstract inspected 1 October 2026; the uniform bound reported there is distinguished from the conjectured sharp bound.