Girã o, Snyder, and Popielarz's linear minimum out-degree conjecture for linked tournaments

Let kk be an integer. A tournament is a digraph obtained by orienting each edge of a complete graph in exactly one direction, and a tournament is rr-connected when deletion of any set of at most r1r-1 vertices leaves a strongly connected digraph. A digraph is kk-linked if, for every 2k2k distinct vertices x1,,xk,y1,,ykx_1,\ldots,x_k,y_1,\ldots,y_k, it contains pairwise vertex-disjoint paths from xix_i to yiy_i for all i[k]i\in[k]. The minimum out-degree is the minimum out-degree among its vertices.

Girã o, Snyder, and Popielarz's conjecture. There exists a constant C>0C>0 such that every (2k+1)(2k+1)-connected tournament with minimum out-degree at least CkCk is kk-linked.

This conjecture asks whether the connectivity bound in the cited theorem can be reduced to 2k+12k+1 while retaining a linear minimum out-degree condition. The supplied text gives no evidence that it has been resolved.

Sources & referencesView supporting material

Primary source

Jia Zhou, Jørgen Bang-Jensen and Jin Yan, “On the k-linkage problem for generalizations of semicomplete digraphs”, arXiv:2503.10295 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.