Transversal Hamilton cycles in digraph collections
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917402189496320 |
|---|---|
| author | Cheng, Yangyang Li, Heng Sun, Wanting Wang, Guanghui |
| author_facet | Cheng, Yangyang Li, Heng Sun, Wanting Wang, Guanghui |
| contents | Given a collection $\mathcal{D} =\{D_1,D_2,\ldots,D_m\}$ of digraphs on the common vertex set $V$, an $m$-edge digraph $H$ with vertices in $V$ is \textit{transversal} in $\mathcal{D}$ if there exists a bijection $φ:E(H)\rightarrow [m]$ such that $e \in E(D_{φ(e)})$ for all $e\in E(H)$. Ghouila-Houri proved that any $n$-vertex digraph with minimum semi-degree at least $\frac{n}{2}$ contains a directed Hamilton cycle. In this paper, we provide a transversal generalization of Ghouila-Houri's theorem, thereby solving a problem proposed by Chakraborti, Kim, Lee and Seo. Our proof utilizes the absorption method for transversals, the regularity method for digraph collections, as well as the transversal blow-up lemma and the related machinery. As an application, when $n$ is sufficiently large, our result implies the transversal version of Dirac's theorem, which was proved by Joos and Kim. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_00998 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Transversal Hamilton cycles in digraph collections Cheng, Yangyang Li, Heng Sun, Wanting Wang, Guanghui Combinatorics 05C20, 05C38 Given a collection $\mathcal{D} =\{D_1,D_2,\ldots,D_m\}$ of digraphs on the common vertex set $V$, an $m$-edge digraph $H$ with vertices in $V$ is \textit{transversal} in $\mathcal{D}$ if there exists a bijection $φ:E(H)\rightarrow [m]$ such that $e \in E(D_{φ(e)})$ for all $e\in E(H)$. Ghouila-Houri proved that any $n$-vertex digraph with minimum semi-degree at least $\frac{n}{2}$ contains a directed Hamilton cycle. In this paper, we provide a transversal generalization of Ghouila-Houri's theorem, thereby solving a problem proposed by Chakraborti, Kim, Lee and Seo. Our proof utilizes the absorption method for transversals, the regularity method for digraph collections, as well as the transversal blow-up lemma and the related machinery. As an application, when $n$ is sufficiently large, our result implies the transversal version of Dirac's theorem, which was proved by Joos and Kim. |
| title | Transversal Hamilton cycles in digraph collections |
| topic | Combinatorics 05C20, 05C38 |
| url | https://arxiv.org/abs/2501.00998 |