Every (13k-6)-strong tournament with minimum out-degree at least 28k-13 is k-linked

2021/08/05 by Bang-Jensen, Jørgen, Johansen, Kasper Skov
#05C20 #05C40 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2108.02639

Abstract

A digraph D is k-linked if it satisfies that for every choice of disjoint sets \x₁,…,x_k\ and \y₁,…,y_k\ of vertices of D there are vertex disjoint paths P₁,…,P_k such that P_i is an (x_i,y_i)-path. Confirming a conjecture by Kühn et al, Pokrovskiy proved in 2015 that every 452k-strong tournament is k-linked and asked for a better linear bound. Very recently Meng et al proved that every (40k-31)-strong tournament is k-linked. In this note we use an important lemma from their paper to give a short proof that every (13k-6)-strong tournament of minimum out-degree at least 28k-13 is k-linked.

Related

• A new connectivity bound for a tournament to be highly linked
• Proof of the linkage conjecture for highly connected tournaments
• Highly linked tournaments
• Solutions to the linkage conjecture in tournaments
• Highly linked tournaments with large minimum out-degree