Rainbow Hamiltonicity in uniformly coloured perturbed digraphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929597167173632 |
|---|---|
| author | Katsamaktsis, Kyriakos Letzter, Shoham Sgueglia, Amedeo |
| author_facet | Katsamaktsis, Kyriakos Letzter, Shoham Sgueglia, Amedeo |
| contents | We investigate the existence of a rainbow Hamilton cycle in a uniformly edge-coloured randomly perturbed digraph. We show that for every $δ\in (0,1)$ there exists $C = C(δ) > 0$ such that the following holds. Let $D_0$ be an $n$-vertex digraph with minimum semidegree at least $δn$ and suppose that each edge of the union of $D_0$ with the random digraph $D(n, p)$ on the same vertex set gets a colour in $[n]$ independently and uniformly at random. Then, with high probability, $D_0 \cup D(n, p)$ has a rainbow directed Hamilton cycle.
This improves a result of Aigner-Horev and Hefetz (2021) who proved the same in the undirected setting when the edges are coloured uniformly in a set of $(1 + \varepsilon)n$ colours. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_09155 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Rainbow Hamiltonicity in uniformly coloured perturbed digraphs Katsamaktsis, Kyriakos Letzter, Shoham Sgueglia, Amedeo Combinatorics We investigate the existence of a rainbow Hamilton cycle in a uniformly edge-coloured randomly perturbed digraph. We show that for every $δ\in (0,1)$ there exists $C = C(δ) > 0$ such that the following holds. Let $D_0$ be an $n$-vertex digraph with minimum semidegree at least $δn$ and suppose that each edge of the union of $D_0$ with the random digraph $D(n, p)$ on the same vertex set gets a colour in $[n]$ independently and uniformly at random. Then, with high probability, $D_0 \cup D(n, p)$ has a rainbow directed Hamilton cycle. This improves a result of Aigner-Horev and Hefetz (2021) who proved the same in the undirected setting when the edges are coloured uniformly in a set of $(1 + \varepsilon)n$ colours. |
| title | Rainbow Hamiltonicity in uniformly coloured perturbed digraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2304.09155 |