Pokrovskiy's strong tournament linking conjecture
Pokrovskiy's strong tournament linking conjecture
A tournament is -strong if deleting fewer than 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 -linked if, for every choice of distinct vertices , there are pairwise vertex-disjoint directed paths from to for . Pokrovskiy's conjecture. For every natural number there exists an integer such that every -strong tournament with minimum in-degree and minimum out-degree at least is -linked.
This conjecture proposes that sufficiently large minimum in-degree and out-degree, together with -strong connectivity, force -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.