Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments

Abstract

A conjecture of Thomassen from 1982 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 Camion, 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^2(k)). 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 Ajtai, Komlós and Szemerédi on asymptotically optimal sorting networks.

34 pages, 3 figures

References in corpus (3)

• Hamilton decompositions of regular expanders: applications
• Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths
• Disjoint paths in tournaments

Cited by in corpus (8)

• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths
• Highly linked tournaments
• Sparse spanning $k$-connected subgraphs in tournaments
• Sparse highly connected spanning subgraphs in dense directed graphs
• Bipartitions of highly connected tournaments
• On 1-factors with prescribed lengths in tournaments