A new connectivity bound for a tournament to be highly linked

Abstract

A digraph $D$ is $k$-linked if for any pair of two disjoint sets $\{x_1,x_2,\dots ,x_k\}$ and $\{y_1,y_2,\dots ,y_k\}$ of vertices in $D$, there exist vertex disjoint dipaths $P_1,P_2,\dots ,P_k$ such that $P_i$ is a dipath from $x_i$ to $y_i$ for each $i\in [k]$. Pokrovskiy (JCTB, 2015) confirmed a conjecture of Kühn et al. (Proc. Lond. Math. Soc., 2014) by verifying that every $452k$-connected tournament is $k$-linked. Meng et al. (Eur. J. Comb., 2021) improved this upper bound by showing that any $(40k-31)$-connected tournament is $k$-linked. In this paper, we show a better upper bound by proving that every $\lceil 12.5k-6\rceil$-connected tournament with minimum out-degree at least $21k-14$ is $k$-linked. Furthermore, we improve a key lemma that was first introduced by Pokrovskiy (JCTB, 2015) and later enhanced by Meng et al. (Eur. J. Comb., 2021).

10 pages