Proof of the linkage conjecture for highly connected tournaments

2025/07/30 by Zhou, Jia, Yan, Jin
#05C20 #05C38 #05C40 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2507.22651

Abstract

A digraph D is k-linked if for every 2k distinct vertices x₁,… , x_k, y₁, … , y_k in D, there exist k pairwise vertex-disjoint paths P₁,…, P_k such that P_i starts at x_i and ends at y_i for each i∈ [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 (k²+11k)/(26) (for k≥ 42). Further, we prove that every (2k+1)-connected semicomplete digraph D with minimum out-degree at least 7k² + 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.

Citations

• On the k-linkage problem for generalizations of semicomplete digraphs
• Solutions to the linkage conjecture in tournaments
• (2k+1)-connected tournaments with large minimum out-degree are\n k-linked
• Highly linked tournaments with large minimum out-degree
• Highly linked tournaments

Related

• Solutions to the linkage conjecture in tournaments
• A new connectivity bound for a tournament to be highly linked
• Every (13k-6)-strong tournament with minimum out-degree at least 28k-13 is k-linked
• Highly linked tournaments
• On the k-linkage problem for generalizations of semicomplete digraphs