Rainbow subgraphs of uniformly coloured randomly perturbed graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912691989250048 |
|---|---|
| author | Katsamaktsis, Kyriakos Letzter, Shoham Sgueglia, Amedeo |
| author_facet | Katsamaktsis, Kyriakos Letzter, Shoham Sgueglia, Amedeo |
| contents | For a given $δ\in (0,1)$, the randomly perturbed graph model is defined as the union of any $n$-vertex graph $G_0$ with minimum degree $δn$ and the binomial random graph $\mathbf{G}(n,p)$ on the same vertex set. Moreover, we say that a graph is uniformly coloured with colours in $\mathcal{C}$ if each edge is coloured independently and uniformly at random with a colour from $\mathcal{C}$.
Based on a coupling idea of McDiarmird, we provide a general tool to tackle problems concerning finding a rainbow copy of a graph $H=H(n)$ in a uniformly coloured perturbed $n$-vertex graph with colours in $[(1+o(1))e(H)]$. For example, our machinery easily allows to recover a result of Aigner-Horev and Hefetz concerning rainbow Hamilton cycles, and to improve a result of Aigner-Horev, Hefetz and Lahiri concerning rainbow bounded-degree spanning trees.
Furthermore, using different methods, we prove that for any $δ\in (0,1)$ and integer $d \ge 2$, there exists $C=C(δ,d)>0$ such that the following holds. Let $T$ be a tree on $n$ vertices with maximum degree at most $d$ and $G_0$ be an $n$-vertex graph with $δ(G_0)\ge δn$. Then a uniformly coloured $G_0 \cup \mathbf{G}(n,C/n)$ with colours in $[n-1]$ contains a rainbow copy of $T$ with high probability. This is optimal both in terms of colours and edge probability (up to a constant factor). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_18284 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Rainbow subgraphs of uniformly coloured randomly perturbed graphs Katsamaktsis, Kyriakos Letzter, Shoham Sgueglia, Amedeo Combinatorics For a given $δ\in (0,1)$, the randomly perturbed graph model is defined as the union of any $n$-vertex graph $G_0$ with minimum degree $δn$ and the binomial random graph $\mathbf{G}(n,p)$ on the same vertex set. Moreover, we say that a graph is uniformly coloured with colours in $\mathcal{C}$ if each edge is coloured independently and uniformly at random with a colour from $\mathcal{C}$. Based on a coupling idea of McDiarmird, we provide a general tool to tackle problems concerning finding a rainbow copy of a graph $H=H(n)$ in a uniformly coloured perturbed $n$-vertex graph with colours in $[(1+o(1))e(H)]$. For example, our machinery easily allows to recover a result of Aigner-Horev and Hefetz concerning rainbow Hamilton cycles, and to improve a result of Aigner-Horev, Hefetz and Lahiri concerning rainbow bounded-degree spanning trees. Furthermore, using different methods, we prove that for any $δ\in (0,1)$ and integer $d \ge 2$, there exists $C=C(δ,d)>0$ such that the following holds. Let $T$ be a tree on $n$ vertices with maximum degree at most $d$ and $G_0$ be an $n$-vertex graph with $δ(G_0)\ge δn$. Then a uniformly coloured $G_0 \cup \mathbf{G}(n,C/n)$ with colours in $[n-1]$ contains a rainbow copy of $T$ with high probability. This is optimal both in terms of colours and edge probability (up to a constant factor). |
| title | Rainbow subgraphs of uniformly coloured randomly perturbed graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2310.18284 |