Projects per year
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 edgedisjoint 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}klogkconnected tournament is klinked (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.
Original language  English 

Pages (fromto)  733762 
Number of pages  30 
Journal  London Mathematical Society. Proceedings 
Volume  109 
Issue number  3 
Early online date  29 May 2014 
DOIs  
Publication status  Published  1 Sept 2014 
Fingerprint
Dive into the research topics of 'Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments'. Together they form a unique fingerprint.Projects
 2 Finished

EdgeColourings and Hamilton Decompostitions of Graphs
Engineering & Physical Science Research Council
1/06/12 → 30/09/14
Project: Research Councils

FP7 ERC  QRGraph: Quasirandomness in Graphs and Hypergraphs
European Commission, European Commission  Management Costs
1/12/10 → 30/11/15
Project: Research