Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.12964 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912075089969152 |
|---|---|
| author | Ferber, Asaf Sales, Marcelo Shurman, Mason |
| author_facet | Ferber, Asaf Sales, Marcelo Shurman, Mason |
| contents | A covering of a digraph $D$ by Hamilton cycles is a collection of directed Hamilton cycles (not necessarily edge-disjoint) that together cover all the edges of $D$. We prove that for $1/2 \geq p\geq \frac{\log^{20} n}{n}$, the random digraph $D_{n,p}$ typically admits an optimal Hamilton cycle covering. Specifically, the edges of $D_{n,p}$ can be covered by a family of $t$ Hamilton cycles, where $t$ is the maximum of the the in-degree and out-degree of the vertices in $D_{n,p}$. Notably, $t$ is the best possible bound, and our assumption on $p$ is optimal up to a polylogarithmic factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_12964 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Covering Random Digraphs with Hamilton Cycles Ferber, Asaf Sales, Marcelo Shurman, Mason Combinatorics A covering of a digraph $D$ by Hamilton cycles is a collection of directed Hamilton cycles (not necessarily edge-disjoint) that together cover all the edges of $D$. We prove that for $1/2 \geq p\geq \frac{\log^{20} n}{n}$, the random digraph $D_{n,p}$ typically admits an optimal Hamilton cycle covering. Specifically, the edges of $D_{n,p}$ can be covered by a family of $t$ Hamilton cycles, where $t$ is the maximum of the the in-degree and out-degree of the vertices in $D_{n,p}$. Notably, $t$ is the best possible bound, and our assumption on $p$ is optimal up to a polylogarithmic factor. |
| title | Covering Random Digraphs with Hamilton Cycles |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.12964 |