ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.