![](/files/happy5.png)
Minimum number of arc-disjoint transitive subtournaments of order 3 in a tournament
Conjecture If
is a tournament of order
, then it contains
arc-disjoint transitive subtournaments of order 3.
![$ T $](/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ \left \lceil n(n-1)/6 - n/3\right\rceil $](/files/tex/559f44f15c03e6e3ad0ebeafb9428b5563c17d28.png)
If true the conjecture would be tight as shown by any tournament whose vertex set can be decomposed into sets
of size
or
and such that
,
and
.
Let denote the transitive tournament of order 3. A
-packing of a digraph
is a set of arc-disjoint copies of
subgraphs of
.
Let be the minimum size of a
-packing over all tournaments of order
. The conjecture and its tightness say
.
The best lower bound for so far is due to Kabiya and Yuster [KY] proved that
.
Bibliography
[KY] M. Kabiya and R. Yuster. Packing transitive triples in a tournament. Ann. Comb. 12 (2008), no. 3, 291–-306.
*[Y] R. Yuster. The number of edge-disjoint transitive triples in a tournament. Discrete Math. 287 (2004). no. 1-3,187--191.
* indicates original appearance(s) of problem.