The exact minimum transitive-triple packing conjecture for tournaments

From papers

Let TnT_n range over all tournaments on nn vertices. Let P(Tn)P(T_n) be the maximum size of a set of edge-disjoint transitive triples in TnT_n, and define

f(n)=minTnP(Tn).f(n)=\min_{T_n}P(T_n).

Exact transitive-triple packing conjecture.

f(n)=n(n1)6n3.f(n)=\left\lceil \frac{n(n-1)}{6}-\frac{n}{3}\right\rceil.

The paper notes that this is an upper bound obtained by an explicit construction and conjectures that it is attained for every nn. The broader problem is to determine the minimum number of edge-disjoint transitive triples guaranteed in an arbitrary tournament; the paper proves a lower bound exceeding 0.13n2(1+o(1))0.13n^2(1+o(1)), leaving the exact formula open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Raphael Yuster, “The number of edge disjoint transitive triples in a tournament”, arXiv:math/0304180 (2003).

Solutions 0

No solutions have been posted yet.