Packing Transitive Triples in a Tournament

We prove that a tournament with n vertices has more than arc-disjoint transitive triples, and more than arc-disjoint transitive quadruples, improving earlier bounds. In particular, 82 percent of the arcs of a tournament can be packed with transitive triples and 45 percent of the arcs of a tournament can be packed with transitive quadruples. Our proof is obtained by examining the fractional version of the problem and utilizing a connection between the integral and fractional versions. Received October 12, 2005