The exact minimum transitive-triple packing conjecture for tournaments

About 23 years old · traced to

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)=min⁡TnP(Tn).f(n)=\min_{T_n}P(T_n).

Exact transitive-triple packing conjecture.

f(n)=⌈n(n−1)6−n3⌉.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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.