Universality for transversal Hamilton cycles in random graphs
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_ | 1866908851408732160 |
|---|---|
| author | Christoph, Micha Martinsson, Anders Milojević, Aleksa |
| author_facet | Christoph, Micha Martinsson, Anders Milojević, Aleksa |
| contents | A tuple $(G_1,\dots,G_n)$ of graphs on the same vertex set of size $n$ is said to be Hamilton-universal if for every map $χ: [n]\to[n]$ there exists a Hamilton cycle whose $i$-th edge comes from $G_{χ(i)}$. Bowtell, Morris, Pehova and Staden proved an analog of Dirac's theorem in this setting, namely that if $δ(G_i)\geq (1/2+o(1))n$ then $(G_1,\dots,G_n)$ is Hamilton-universal. Combining McDiarmid's coupling and a colorful version of the Friedman-Pippenger tree embedding technique, we establish a similar result in the setting of sparse random graphs, showing that there exists $C$ such that if the $G_i$ are independent random graphs sampled from $G(n,p)$, where $p\geq C\log n/n$, then $(G_1,\dots,G_n)$ is Hamilton-universal with high probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05385 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Universality for transversal Hamilton cycles in random graphs Christoph, Micha Martinsson, Anders Milojević, Aleksa Combinatorics 05C80, 05C45, 05D15 A tuple $(G_1,\dots,G_n)$ of graphs on the same vertex set of size $n$ is said to be Hamilton-universal if for every map $χ: [n]\to[n]$ there exists a Hamilton cycle whose $i$-th edge comes from $G_{χ(i)}$. Bowtell, Morris, Pehova and Staden proved an analog of Dirac's theorem in this setting, namely that if $δ(G_i)\geq (1/2+o(1))n$ then $(G_1,\dots,G_n)$ is Hamilton-universal. Combining McDiarmid's coupling and a colorful version of the Friedman-Pippenger tree embedding technique, we establish a similar result in the setting of sparse random graphs, showing that there exists $C$ such that if the $G_i$ are independent random graphs sampled from $G(n,p)$, where $p\geq C\log n/n$, then $(G_1,\dots,G_n)$ is Hamilton-universal with high probability. |
| title | Universality for transversal Hamilton cycles in random graphs |
| topic | Combinatorics 05C80, 05C45, 05D15 |
| url | https://arxiv.org/abs/2505.05385 |