Highly linked tournaments with large minimum out-degree

摘要

We prove that there exists a function f : N -> N such that for any positive integer k, if T is a strongly 4k-connected tournament with minimum out-degree at least f (k), then T is k-linked. This resolves a conjecture of Pokrovskiy up to a factor of 2 of the required connectivity. Along the way, we show that a tournament with sufficiently large minimum out-degree contains a subdivision of a complete directed graph. This result may be of independent interest. (C) 2019 Elsevier Inc. All rights reserved.