Proof of the linkage conjecture for highly connected tournaments

Abstract

A digraph $D$ is $k$-linked if for every $2k$ distinct vertices $x_1,\dots ,x_k,y_1,\dots ,y_k$ in $D$, there exist $k$ pairwise vertex-disjoint paths $P_1,\dots ,P_k$ such that $P_i$ starts at $x_i$ and ends at $y_i$ for each $i\in [k]$. In 2021, Girão, Popielarz, and Snyder [Combinatorica 41 (2021) 815--837] conjectured that there exists a constant $C>0$ such that every $(2k+1)$-connected tournament with minimum out-degree at least $Ck$ is $k$-linked. In this paper, we disprove this conjecture by constructing a family of counterexamples with minimum out-degree at least $\frac{k^2+11k}{26}$ (for $k\ge 42$). Further, we prove that every $(2k+1)$-connected semicomplete digraph $D$ with minimum out-degree at least $7k^2+36k$ is $k$-linked. This result is optimal in terms of both connectivity and minimum out-degree (up to a multiplicative factor), which refines and generalizes the earlier result of Girão, Popielarz, and Snyder.

16 pages,4 figures