Highly linked tournaments

Abstract

A (possibly directed) graph is $k$-linked if for any two disjoint sets of vertices $\{x_1,\dots ,x_k\}$ and $\{y_1,\dots ,y_k\}$ there are vertex disjoint paths $P_1,\dots ,P_k$ such that $P_i$ goes from $x_i$ to $y_i$. A theorem of Bollobás and Thomason says that every $22k$-connected (undirected) graph is $k$-linked. It is desirable to obtain analogues for directed graphs as well. Although Thomassen showed that the Bollobás-Thomason Theorem does not hold for general directed graphs, he proved an analogue of the theorem for tournaments - there is a function $f(k)$ such that every strongly $f(k)$-connected tournament is $k$-linked. The bound on $f(k)$ was reduced to $O(k\log k)$ by Kühn, Lapinskas, Osthus, and Patel, who also conjectured that a linear bound should hold. We prove this conjecture, by showing that every strongly $452k$-connected tournament is $k$-linked.

8 pages

Cited by in corpus (1)

• Bipartitions of highly connected tournaments