Pokrovskiy's semidegree conjecture for linked tournaments

Let kNk\in\mathbb{N}. A tournament is a digraph obtained by orienting each edge of a complete graph in exactly one direction. For a tournament DD, let δ+(D)\delta^+(D) and δ(D)\delta^-(D) denote its minimum out-degree and minimum in-degree, respectively, and let

δ0(D)=min{δ+(D),δ(D)}\delta^0(D)=\min\{\delta^+(D),\delta^-(D)\}

denote its minimum semidegree. A tournament is kk-linked if every 2k2k distinct vertices can be paired in the prescribed order by kk pairwise vertex-disjoint directed paths.

Pokrovskiy's conjecture. For every kNk\in\mathbb{N}, there exists an integer h(k)h(k) such that every 2k2k-connected tournament with δ0(D)h(k)\delta^0(D)\geq h(k) is kk-linked.

The conjecture was disproved by a family of 2k2k-connected tournaments with sufficiently large order and minimum semidegree that are not kk-linked. Thus connectivity at least 2k+12k+1 is necessary when the minimum semidegree is prescribed as a function of kk.

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

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.