Packing Transitive Triples in a
Tournament

Mohamad Kabiya and Raphael Yuster

Department of Mathematics,
University of Haifa, Haifa 31905, Israel
mkabiya@yahoo.com, raphy@research.haifa.ac.il

Annals of Combinatorics 12 (3) pp.291-306 September, 2008

Abstract:

We prove that a tournament with
$n$ vertices has more than $\frac{41}{300}n^2(1-o(1))$
arc-disjoint transitive triples, and more than
$\frac{113}{3000}n^2(1-o(1))$ 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.
References:

1. N. Alon and A. Shapira, Testing subgraphs in directed graphs, In: Proceedings of the Thirty- Fifth Annual ACM Symposium on Theory of Computing, ACM Press, New York, (2003) pp. 700-709.

2. B. Bollob´as, Extremal Graph Theory, Academic Press, New York, 1978.

3. A. Czygrinow, S. Poljak, and V. R¨odl, Constructive Quasi-Ramsey numbers and tournament ranking, SIAM J. Discrete Math. 12 (1) (1999) 48-63.

4. D. Dor and M. Tarsi, Graph decomposition is NPC a complete proof of Holyer's conjecture, In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, ACM Press, New York, (1992) pp. 252-263.

5. P. Frankl and V. R¨odl, Near perfect coverings in graphs and hypergraphs, European J. Combin. 6 (4) (1985) 317-326.

6. P.E. Haxell and V. R¨odl, Integer and fractional packings in dense graphs, Combinatorica 21 (1) (2001) 13-38.

7. R.B. Gardner, Optimal packings and coverings of the complete directed graph with 3-circuits and with transitive triples, Congr. Numer. 127 (1997) 161-170.

8. P. Keevash and B. Sudakov, Packing triangles in a graph and its complement, J. Graph Theory 47 (3) (2004) 203-216.

9. Z. Nutov and R. Yuster, Packing directed cycles efciently, Discrete Appl. Math. 155 (2) (2007) 82-91.

10. K.T. Phelps and C.C. Lindner, On the number of Mendelsohn and transitive triple systems, European J. Combin. 5 (3) (1984) 239-242.

11. K.B. Reid and E.T. Parker, Disproof of a conjecture of Erdos and Moser on tournaments, J. Combin. Theory 9 (1970) 225-238.

12. D.B. Skillicorn, A note on directed packings of pairs into triples, Ars Combin. 13 (1982) 227-229.

13. E. Szemer´edi, Regular partitions of graphs, In: Problemes Combinatoires et Th´eorie des Graphes, Colloq. Internat. CNRS, Vol. 260, J.-C. Bermond, J.-C. Fournier, M. Las Vergnas, and D. Sotteau, Eds., CNRS, Paris, (1978) pp. 399-401.

14. R. Yuster, The number of edge-disjoint transitive triples in a tournament, Discrete Math. 287 (1-3) (2004) 187-191.

15. R. Yuster, Integer and fractional packing of families of graphs, Random Structures Algorithms 26 (1-2) (2005) 110-118.

16. R. Yuster, Asymptotically optimal Kk-packing of dense graphs via fractional Kk decompositions, J. Combin. Theory Ser. B 95 (1) (2005) 1-11.

17. R. Yuster, Decomposing oriented graphs into transitive tournaments, Discrete Math. 306 (1) (2006) 166-170.