we-solve (beta)

Math-1056 · mathematics · Graph theory

Minimum number of arc-disjoint transitive subtournaments of order 3 in a tournament

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

A tournament of order $n\geq1$ is a directed graph with $n$ vertices, no loops, and exactly one of the arcs $u\to v$ and $v\to u$ for each pair of distinct vertices. A transitive triple is a three-vertex subtournament whose vertices can be ordered $a,b,c$ with arcs $a\to b$, $a\to c$, and $b\to c$. Thus its three arcs do not form a directed cycle.

A packing of transitive triples is a collection of such triples whose arc sets are pairwise disjoint. Different triples may share a vertex, but no pair can share two vertices, but cannot reuse any directed edge. Write $\nu_T(T)$ for the largest number of triples in a packing in $T$ and define \[ f(n)=\min\{\nu_T(T):T\text{ is a tournament on }n\text{ vertices}\}. \] The maximum inside this minimum is essential: an arbitrary packing could always be empty.

The conjectured guarantee is that every tournament $T$ of order $n$ satisfies \[ \nu_T(T)\geq \left\lceil\frac{n(n-1)}6-\frac n3\right\rceil =\left\lceil\frac{n(n-3)}6\right\rceil. \] The ceiling denotes the least integer greater than or equal to its argument. The assertion asks for one simultaneous packing of this size; counting all transitive triples without controlling their overlap is insufficient. Since each selected triple uses three arcs, the scale of the proposed bound is one third of all arcs in the tournament, with a linear correction.

Short English statement

Can every tournament pack at least the stated number of transitive triples without reusing an arc?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-1056-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-1056

Minimum number of arc-disjoint transitive subtournaments of order 3 in a tournament

Definitions and mathematical statement

A tournament of order $n\geq1$ is a directed graph with $n$ vertices, no loops, and exactly one of the arcs $u\to v$ and $v\to u$ for each pair of distinct vertices. A transitive triple is a three-vertex subtournament whose vertices can be ordered $a,b,c$ with arcs $a\to b$, $a\to c$, and $b\to c$. Thus its three arcs do not form a directed cycle.

A packing of transitive triples is a collection of such triples whose arc sets are pairwise disjoint. Different triples may share a vertex, but no pair can share two vertices, but cannot reuse any directed edge. Write $\nu_T(T)$ for the largest number of triples in a packing in $T$ and define \[ f(n)=\min\{\nu_T(T):T\text{ is a tournament on }n\text{ vertices}\}. \] The maximum inside this minimum is essential: an arbitrary packing could always be empty.

The conjectured guarantee is that every tournament $T$ of order $n$ satisfies \[ \nu_T(T)\geq \left\lceil\frac{n(n-1)}6-\frac n3\right\rceil =\left\lceil\frac{n(n-3)}6\right\rceil. \] The ceiling denotes the least integer greater than or equal to its argument. The assertion asks for one simultaneous packing of this size; counting all transitive triples without controlling their overlap is insufficient. Since each selected triple uses three arcs, the scale of the proposed bound is one third of all arcs in the tournament, with a linear correction.

Short English statement

Can every tournament pack at least the stated number of transitive triples without reusing an arc?

Research attempt

Scope and process.
This is a GPT-6 Astra Ultra research attempt dated 1 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.
Literature and approach.
The original source [S2, R1] attributes the conjecture to Yuster and describes a balanced cyclic three-part construction showing the proposed bound is sharp. We verify that obstruction, then give a self-contained packing guarantee from a maximal packing. The guarantee is weaker than the conjecture and than sophisticated published packing bounds; its purpose is to isolate the loss in a simple greedy attack.
A sharp obstruction to any stronger proposed bound.
Partition the vertices into $V_1,V_2,V_3$ as equally as possible and orient all cross-arcs cyclically, $V_1\to V_2\to V_3\to V_1$. Orient within the parts arbitrarily. A triple with one vertex in each part is cyclic, so every transitive triple uses an arc internal to some $V_i$. Arc-disjoint triples use distinct such internal arcs. Consequently every packing has size at most \[ \sum_{i=1}^3\binom{|V_i|}{2} =\left\lceil\frac{n(n-3)}6\right\rceil \qquad(n\ge2). \] For the identity, put $n=3q+r$ with $0\le r<3$ and use $r$ parts of size $q+1$ and $3-r$ of size $q$. This proves the upper obstruction, not existence of a packing reaching it in every orientation. For $n=1$ both the actual packing number and the proposed ceiling are zero, separately.
What a maximal packing leaves behind.
Start with any packing to which no additional arc-disjoint transitive triple can be added. Delete its $3k$ arcs and ignore the directions of the remaining arcs, obtaining a simple graph $R$. This graph contains no $K_4$. Indeed, if four vertices retained all six arcs, their induced tournament would contain a transitive triple: at any one vertex at least two of the other three are both out-neighbours or both in-neighbours, and those three vertices form such a triple regardless of the direction of their remaining arc. It could have been added to the packing, contradicting maximality.
An elementary bound for the residual graph.
We prove that a $K_4$-free graph on $n$ vertices has at most $n^2/3$ edges. If it has no triangle, every edge $uv$ satisfies $d(u)+d(v)\le n$, because the two neighbourhoods are disjoint. Summing over edges gives $\sum_vd(v)^2\le ne$; Cauchy--Schwarz gives $4e^2/n\le\sum_vd(v)^2$, and hence $e\le n^2/4$ (the case $e=0$ is immediate). Otherwise choose a triangle. Every outside vertex has at most two neighbours in it, so deleting the triangle removes at most $3+2(n-3)=2n-3$ edges. Induction on $n$ now gives \[ e\le(n-3)^2/3+(2n-3)=n^2/3. \] The base cases $n\le3$ satisfy the bound directly.

Apply this to $R$. Since $|E(R)|=\binom n2-3k$, \[ k\ge\left\lceil\frac{n(n-3)}{18}\right\rceil. \] Any inclusion-maximal packing meets this weaker guarantee, so the maximum packing does too. The conjecture would require roughly three times as many triples; the residual extremal bound alone therefore leaves a substantial quadratic gap.

Finite verification and what it establishes.
The exact script scripts/check_attempt_batch02_algebra_2026_10_01.py enumerates all orientations for $n\le5$. For each it lists the transitive three-vertex sets and computes the maximum collection of pairwise disjoint arc masks by exhaustive recursion. The resulting minimum packing numbers for $n=1,2,3,4,5$ are $0,0,0,1,2$, matching the proposed ceilings. This checks the small instances and the maximum/minimum quantifiers, not the asymptotic conjecture.
Verification and first remaining gap.
Maximal does not mean maximum; only the absence of an additional disjoint triple was used in the residual argument. Removing three arcs per chosen triple is legitimate because their arc sets are disjoint, even though they can share vertices. The obstruction construction counts a necessary internal arc, not an arbitrary three-vertex set. To improve the lower bound to the proposed one, one needs an exchange or absorption argument that replaces selected triples and controls the residual orientation. Merely counting all available triples or declaring the residual $K_4$-free cannot do so.
Final status.
UNRESOLVED. The sharp upper obstruction, an explicit weaker universal packing bound, and the finite cases through order five are verified; no all-order matching lower bound is proved.

Sources

Go to contribution →