Solutions to the linkage conjecture in tournaments
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912152143527936 |
|---|---|
| author | Zhou, Jia Yan, Jin |
| author_facet | Zhou, Jia Yan, Jin |
| contents | A digraph $D$ is $k$-linked if for every $2k$-tuple $ x_1,\ldots , x_k, y_1, \ldots , y_k$ of distinct vertices in $D$, there exist $k$ pairwise vertex-disjoint paths $P_1,\ldots, P_k$ such that $P_i$ starts at $x_i$ and ends at $y_i$, $i\in [k]$. In 2015, Pokrovskiy conjectured that there exists a function $g(k)$ such that every $2k$-connected tournament with minimum in-degree and minimum out-degree at least $g(k)$ is $k$-linked in [J. Comb. Theory, Ser. B 115 (2015) 339--347]. In this paper, we disprove this conjecture by constructing a family of counterexamples. The counterexamples also provide a negative answer to the question raised by Girão, Popielarz, Snyder in [Combinatorica 41 (2021) 815--837]. Further, we prove that every $(2k+1)$-connected semicomplete digraph $D$ with minimum out-degree at least $ 10^7k^{4}$ is $k$-linked, which refines and generalizes the early result of Girão, Popielarz, Snyder. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_08180 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Solutions to the linkage conjecture in tournaments Zhou, Jia Yan, Jin Combinatorics 05C20, 05C38, 05C40 A digraph $D$ is $k$-linked if for every $2k$-tuple $ x_1,\ldots , x_k, y_1, \ldots , y_k$ of distinct vertices in $D$, there exist $k$ pairwise vertex-disjoint paths $P_1,\ldots, P_k$ such that $P_i$ starts at $x_i$ and ends at $y_i$, $i\in [k]$. In 2015, Pokrovskiy conjectured that there exists a function $g(k)$ such that every $2k$-connected tournament with minimum in-degree and minimum out-degree at least $g(k)$ is $k$-linked in [J. Comb. Theory, Ser. B 115 (2015) 339--347]. In this paper, we disprove this conjecture by constructing a family of counterexamples. The counterexamples also provide a negative answer to the question raised by Girão, Popielarz, Snyder in [Combinatorica 41 (2021) 815--837]. Further, we prove that every $(2k+1)$-connected semicomplete digraph $D$ with minimum out-degree at least $ 10^7k^{4}$ is $k$-linked, which refines and generalizes the early result of Girão, Popielarz, Snyder. |
| title | Solutions to the linkage conjecture in tournaments |
| topic | Combinatorics 05C20, 05C38, 05C40 |
| url | https://arxiv.org/abs/2412.08180 |