<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 3" %>
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
AMS Subject Classification: 05C20, 05C70
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.
Keywords: tournament, packing, fractional

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.