2019/12/02 by António Girão, Girão, António, Kamil Popielarz +3 · 1 citation
Computer Science · Mathematics · #Algebraic structures and combinatorial models #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Cooperative Communication and Network Coding #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1912.00710
openalex publication_date 2019/12/02 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
Pokrovskiy conjectured that there is a function f: \ℕ \→\n\ℕ such that any 2k-strongly-connected tournament with minimum out\nand in-degree at least f(k) is k-linked. In this paper, we show that any\n(2k+1)-strongly-connected tournament with minimum out-degree at least some\npolynomial in k is k-linked, thus resolving the conjecture up to the\nadditive factor of 1 in the connectivity bound, but without the extra\nassumption that the minimum in-degree is large. Moreover, we show the condition\non high minimum out-degree is necessary by constructing arbitrarily large\ntournaments that are (2.5k-1)-strongly-connected but are not k-linked.\n