$(2k+1)$-connected tournaments with large minimum out-degree are $k$-linked

Abstract

Pokrovskiy conjectured that there is a function $f:\mathbb{N}\to \mathbb{N}$ such that any $2k$-strongly-connected tournament with minimum out and in-degree at least $f(k)$ is $k$-linked. In this paper, we show that any $(2k+1)$-strongly-connected tournament with minimum out-degree at least some polynomial in $k$ is $k$-linked, thus resolving the conjecture up to the additive factor of $1$ in the connectivity bound, but without the extra assumption that the minimum in-degree is large. Moreover, we show the condition on high minimum out-degree is necessary by constructing arbitrarily large tournaments that are $(2.5k-1)$-strongly-connected but are not $k$-linked.

15 pages, 2 figures