Solutions to the linkage conjecture in tournaments

Abstract

A digraph $D$ is $k$-linked if for every $2k$-tuple $x_1,\dots ,x_k,y_1,\dots ,y_k$ of distinct vertices 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$, $i\in [k]$. In 2015, Pokrovskiy conjectured that there exists a function $g(k)$ such that every $2k$-connected tournament with minimum in-degree and minimum out-degree at least $g(k)$ is $k$-linked in [J. Comb. Theory, Ser. B 115 (2015) 339--347]. In this paper, we disprove this conjecture by constructing a family of counterexamples. The counterexamples also provide a negative answer to the question raised by Girão, Popielarz, Snyder in [Combinatorica 41 (2021) 815--837]. Further, we prove that every $(2k+1)$-connected semicomplete digraph $D$ with minimum out-degree at least $10^7{k}^4$ is $k$-linked, which refines and generalizes the early result of Girão, Popielarz, Snyder.

24pages, 6 figures