Pokrovskiy's semidegree conjecture for linked tournaments
Pokrovskiy's semidegree conjecture for linked tournaments
Let . A tournament is a digraph obtained by orienting each edge of a complete graph in exactly one direction. For a tournament , let and denote its minimum out-degree and minimum in-degree, respectively, and let
denote its minimum semidegree. A tournament is -linked if every distinct vertices can be paired in the prescribed order by pairwise vertex-disjoint directed paths.
Pokrovskiy's conjecture. For every , there exists an integer such that every -connected tournament with is -linked.
The conjecture was disproved by a family of -connected tournaments with sufficiently large order and minimum semidegree that are not -linked. Thus connectivity at least is necessary when the minimum semidegree is prescribed as a function of .
Sources & referencesView supporting material
Primary source
Jia Zhou and Jin Yan, “Proof of the linkage conjecture for highly connected tournaments”, arXiv:2507.22651 (2025).
Additional references
4 papers in this index state this conjecture (2023–2025). The statement above is taken from the most recent of them; the others are arXiv:2503.10295, arXiv:2412.08180, arXiv:2311.04068.
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.