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

D. Kuhn, J. Lapinskas, D. Osthus, V. Patel

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)
189 Downloads (Pure)

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(k2log2k). This is best possible up to the logarithmic factor. As a tool, we show that every strongly 104klogk-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.
Original languageEnglish
Pages (from-to)733-762
Number of pages30
JournalLondon Mathematical Society. Proceedings
Volume109
Issue number3
Early online date29 May 2014
DOIs
Publication statusPublished - 1 Sep 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.

Cite this