Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2310.08449 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916818558386176 |
|---|---|
| author | Christoph, Micha Petrova, Kalina Steiner, Raphael |
| author_facet | Christoph, Micha Petrova, Kalina Steiner, Raphael |
| contents | A tantalizing open problem, posed independently by Stiebitz in 1995 and by Alon in 2006, asks whether for every pair of integers $s,t \ge 1$ there exists a finite number $F(s,t)$ such that the vertex set of every digraph of minimum out-degree at least $F(s,t)$ can be partitioned into non-empty parts $A$ and $B$ such that the subdigraphs induced on $A$ and $B$ have minimum out-degree at least $s$ and $t$, respectively.
In this short note, we prove that if $F(2,2)$ exists, then all the numbers $F(s,t)$ with $s,t\ge 1$ exist and satisfy $F(s,t)=Θ(s+t)$. In consequence, the problem of Alon and Stiebitz reduces to the case $s=t=2$. Moreover, the numbers $F(s,t)$ with $s,t \ge 2$ either all exist and grow linearly, or all of them do not exist. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_08449 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A note on digraph splitting Christoph, Micha Petrova, Kalina Steiner, Raphael Combinatorics A tantalizing open problem, posed independently by Stiebitz in 1995 and by Alon in 2006, asks whether for every pair of integers $s,t \ge 1$ there exists a finite number $F(s,t)$ such that the vertex set of every digraph of minimum out-degree at least $F(s,t)$ can be partitioned into non-empty parts $A$ and $B$ such that the subdigraphs induced on $A$ and $B$ have minimum out-degree at least $s$ and $t$, respectively. In this short note, we prove that if $F(2,2)$ exists, then all the numbers $F(s,t)$ with $s,t\ge 1$ exist and satisfy $F(s,t)=Θ(s+t)$. In consequence, the problem of Alon and Stiebitz reduces to the case $s=t=2$. Moreover, the numbers $F(s,t)$ with $s,t \ge 2$ either all exist and grow linearly, or all of them do not exist. |
| title | A note on digraph splitting |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2310.08449 |