Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments. Issue 3 (29th May 2014)

• Record Type: Journal Article
• Authors: Kühn, Daniela; Lapinskas, John; Osthus, Deryk; Patel, Viresh
• Is Part Of: Proceedings of the London Mathematical Society. Volume 109:Issue 3(2014:Sep.)
• Page Start: 733
• Page End: 762
• Publication Date: 2014-05-29
• Subjects: Mathematics -- Periodicals; Mathematics; Periodicals; 510
• DOI: 10.1112/plms/pdu019
• Languages: English
• ISSNs: 0024-6115

Abstract

Abstract : A conjecture of Thomassen from 1982 states that, for everyk, there is anf ( k ) so that every stronglyf ( k ) ‐connected tournament containsk edge‐disjoint Hamilton cycles. A classical theorem of Camion, that every strongly connected tournament contains a Hamilton cycle, implies thatf ( 1 ) = 1 . So far, even the existence off ( 2 ) was open. In this paper, we prove Thomassen's conjecture by showing thatf ( k ) = O ( k 2 log 2 k ) . This is best possible up to the logarithmic factor. As a tool, we show that every strongly10 4 k log k ‐connected tournament isk ‐linked (which improves a previous exponential bound). The proof of the latter is based on a fundamental result of Ajtai, Komlós and Szemerédi on asymptotically optimal sorting networks.