×

zbMATH — the first resource for mathematics

Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments. (English) Zbl 1302.05069
Summary: A conjecture of C. Thomassen [Proc. Lond. Math. Soc., III. Ser. 45, 151–168 (1982; Zbl 0486.05049)] states that, for every \(k\), there is an \(f(k)\) so that every strongly \(f(k)\)-connected tournament contains \(k\) edge-disjoint Hamilton cycles. A classical theorem of P. Camion [C. R. Acad. Sci., Paris 249, 2151–2152 (1959; Zbl 0092.15801)], that every strongly connected tournament contains a Hamilton cycle, implies that \(f(1)=1\). So far, even the existence of \(f(2)\) was open. In this paper, we prove Thomassen’s conjecture by showing that \(f(k)=O(k^2 \log ^2k)\). This is best possible up to the logarithmic factor. As a tool, we show that every strongly \(10^4 k \log k\)-connected tournament is \(k\)-linked (which improves a previous exponential bound). The proof of the latter is based on a fundamental result of M. Ajtai et al. [Combinatorica 3, 1–19 (1983; Zbl 0523.68048)] on asymptotically optimal sorting networks.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory
05C40 Connectivity
05C45 Eulerian and Hamiltonian graphs
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Ajtai, Sorting in ClogN parallel steps, Combinatorica 3 pp 1– (1983) · Zbl 0523.68048 · doi:10.1007/BF02579338
[2] M. Ajtai J. Komlós E. Szemerédi An O ( n log n ) sorting network Proc. 15th Ann. ACM Symp. on Theory of Computing ACM, New York, USA 1983 1 9
[3] Bang-Jensen, On the 2-linkage problem for semicomplete digraphs, Ann. Discrete Math. 41 pp 23– (1989) · Zbl 0664.05034 · doi:10.1016/S0167-5060(08)70447-3
[4] Bang-Jensen, Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs, Discrete Math. 309 pp 5655– (2009) · Zbl 1207.05067 · doi:10.1016/j.disc.2008.04.016
[5] Bang-Jensen, Digraphs: theory, algorithms and applications (2008)
[6] Bang-Jensen, A polynomial algorithm for the 2-path problem for semicomplete digraphs, SIAM J. Discrete Math. 5 pp 366– (1992) · Zbl 0759.05041 · doi:10.1137/0405027
[7] K. E. Batcher Sorting networks and their applications Proceedings of the AFIPS Spring Joint Computer Conference ACM, New York, USA 1968 307 314
[8] Bollobás, Highly linked graphs, Combinatorica 16 pp 313– (1996) · Zbl 0870.05044 · doi:10.1007/BF01261316
[9] Bondy, Graph theory (2008) · doi:10.1007/978-1-84628-970-5
[10] Camion, Chemins et circuits hamiltoniens des graphes complets, C. R. Acad. Sci. Paris 249 pp 2151– (1959) · Zbl 0092.15801
[11] M. Chudnovsky A. Scott P. Seymour Disjoint paths in tournaments http://people.maths.ox.ac.uk/scott/Papers/disjointpaths.pdf
[12] A. Ferber M. Krivelevich B. Sudakov Counting and packing Hamilton cycles in dense graphs and oriented graphs http://arxiv.org/pdf/1212.4667.pdf · Zbl 1350.05063
[13] Fortune, The directed subgraph homeomorphism problem, J. Theoret. Comput. Sci. 10 pp 111– (1980) · Zbl 0419.05028 · doi:10.1016/0304-3975(80)90009-2
[14] Knuth, The art of computer programming (1997) · Zbl 0895.68055
[15] Krivelevich, Triangle factors in random graphs, Combin. Probab. Comput. 6 pp 337– (1997) · Zbl 0886.05101 · doi:10.1017/S0963548397003106
[16] Kühn, Optimal packings of Hamilton cycles in graphs of high minimum degree, Combin. Probab. Comput. 22 pp 394– (2013) · Zbl 1269.05068 · doi:10.1017/S0963548312000569
[17] Kühn, A survey on Hamilton cycles in directed graphs, European J. Combin. 33 pp 750– (2012) · Zbl 1239.05114 · doi:10.1016/j.ejc.2011.09.030
[18] Kühn, Hamilton decompositions of regular expanders: a proof of Kelly’s conjecture for large tournaments, Adv. Math. 237 pp 62– (2013) · Zbl 1261.05053 · doi:10.1016/j.aim.2013.01.005
[19] Kühn, Hamilton decompositions of regular expanders: applications, J. Combin. Theory B 104 pp 1– (2014) · Zbl 1282.05084 · doi:10.1016/j.jctb.2013.10.006
[20] D. Kühn D. Osthus T. Townsend Proof of a tournament partition conjecture and an application to 1 -factors with prescribed cycle lengths http://arxiv.org/pdf/1309.7677.pdf · Zbl 1389.05058
[21] Moon, On subtournaments of a tournament, Canad. Math. Bull. 9 pp 297– (1966) · Zbl 0141.41204 · doi:10.4153/CMB-1966-038-7
[22] Paterson, Improved sorting networks with O(logN) depth, Algorithmica 5 pp 75– (1990) · Zbl 0689.68066 · doi:10.1007/BF01840378
[23] Reid, Three problems on tournaments, Graph Theory Appl. East West, Ann. New York Acad. Sci. 576 pp 466– (1989) · doi:10.1111/j.1749-6632.1989.tb16430.x
[24] Rödl, A Dirac-type theorem for 3-uniform hypergraphs, Combin. Probab. Comput. 15 pp 229– (2006) · Zbl 1082.05057 · doi:10.1017/S0963548305007042
[25] Thomas, An improved extremal function for graph linkages, European J. Combin. 26 pp 309– (2005) · Zbl 1056.05091 · doi:10.1016/j.ejc.2004.02.013
[26] Thomassen, edge-disjoint Hamiltonian paths and cycles in tournaments, Proc. London Math. Soc. 45 pp 151– (1982) · Zbl 0486.05049 · doi:10.1112/plms/s3-45.1.151
[27] Thomassen, Connectivity in tournaments, Graph theory and combinatorics, A volume in honour of Paul Erdos pp 305– (1984)
[28] Thomassen, Note on highly connected non-2-linked digraphs, Combinatorica 11 pp 393– (1991) · Zbl 0746.05030 · doi:10.1007/BF01275674
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.