Pokrovskiy's strong tournament linking conjecture

A tournament is rr-strong if deleting fewer than rr vertices leaves a strongly connected tournament, and its minimum in-degree and minimum out-degree are the least in-degree and out-degree among its vertices. A tournament is kk-linked if, for every choice of distinct vertices x1,,xk,y1,,ykx_1,\ldots,x_k,y_1,\ldots,y_k, there are pairwise vertex-disjoint directed paths from xix_i to yiy_i for i=1,,ki=1,\ldots,k. Pokrovskiy's conjecture. For every natural number kk there exists an integer d(k)d(k) such that every 2k2k-strong tournament with minimum in-degree and minimum out-degree at least d(k)d(k) is kk-linked.

This conjecture proposes that sufficiently large minimum in-degree and out-degree, together with 2k2k-strong connectivity, force kk-linkedness in tournaments. The source presents it as a conjecture of Pokrovskiy; no resolution is given in the supplied text.

Sources & referencesView supporting material

Primary source

Jørgen Bang-Jensen and Kasper Skov Johansen, “Every (13k-6)-strong tournament with minimum out-degree at least 28k-13 is k-linked”, arXiv:2108.02639 (2021).

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.