Rainbow spanning trees in uniformly coloured perturbed graphs

EUROCOMB’23

Kyriakos Katsamaktsis Shoham Letzter Amedeo Sgueglia

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-090

PDF
Abstract
We consider the problem of finding a copy of a rainbow spanning bounded-degree tree in the uniformly edge-coloured randomly perturbed graph. Let $G_0$ be an $n$-vertex graph with minimum degree at least $\delta n$, and let $T$ be a tree on $n$ vertices with maximum degree at most $d$, where $\delta \in (0,1)$ and $d \ge 2$ are constants. We show that there exists $C = C(\delta, d) > 0$ such that, with high probability, if the edges of the union $G_0 \cup \mathbf{G}(n,C/n)$ are uniformly coloured with colours in $[n-1]$, then there is a rainbow copy of $T$. Our result resolves in a strong form a conjecture of Aigner-Horev, Hefetz and Lahiri.

Pages:
653–658
References

Aigner-Horev, E., D. Hefetz, and A. Lahiri. 2023. "Rainbow Trees in Uniformly Edge-Colored Graphs." Random Structures & Algorithms 62 (2): 287-303.
https://doi.org/10.1002/rsa.21103

Alon, N., M. Krivelevich, and B. Sudakov. 2007. "Embedding Nearly-Spanning Bounded Degree Trees." Combinatorica 27 (6): 629-44.
https://doi.org/10.1007/s00493-007-2182-z

Bal, D., and A. Frieze. 2016. "Rainbow matchings and Hamilton cycles in random graphs." Random Structures & Algorithms 48 (3): 503-23.
https://doi.org/10.1002/rsa.20594

Bohman, T., A. Frieze, and R. Martin. 2003. "How many random edges make a dense graph Hamiltonian?" Random Structures & Algorithms 22 (1): 33-42. https://doi.org/https://doi.org/10.1002/rsa.10070.
https://doi.org/10.1002/rsa.10070

Ferber, A. 2015. "Closing Gaps in Problems Related to Hamilton Cycles in Random Graphs and Hypergraphs." Electronic Journal of Combinatorics 22 (1): Paper 1.61, 7 pp.
https://doi.org/10.37236/5025

Ferber, A., and M. Krivelevich. 2016. "Rainbow Hamilton cycles in random graphs and hypergraphs." In Recent Trends in Combinatorics, 159:167-89. Springer.
https://doi.org/10.1007/978-3-319-24298-9_7

Frieze, A., and P.-S. Loh. 2014. "Rainbow Hamilton cycles in random graphs." Random Structures & Algorithms 44 (3): 328-54.
https://doi.org/10.1002/rsa.20475

Gould, S., T. Kelly, D. Kühn, and D. Osthus. 2022. "Almost all optimally coloured complete graphs contain a rainbow Hamilton path." Journal of Combinatorial Theory, Series B 156: 57-100.
https://doi.org/10.1016/j.jctb.2022.04.003

Katsamaktsis, K., and S. Letzter. 2022. "Rainbow Hamiltonicity in uniformly coloured perturbed graphs." arXiv:2304.09155.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-090

Katsamaktsis, K., S. Letzter, and A. Sgueglia. n.d. "Rainbow directed Hamilton cycles in uniformly coloured perturbed digraphs." In Preparation.

Krivelevich, M. 2010. "Embedding Spanning Trees in Random Graphs." SIAM Journal on Discrete Mathematics 24 (4): 1495-1500.
https://doi.org/10.1137/100805753

Krivelevich, M., M. Kwan, and B. Sudakov. 2017. "Bounded-Degree Spanning Trees in Randomly Perturbed Graphs." SIAM Journal on Discrete Mathematics 31 (1): 155-71.
https://doi.org/10.1137/15M1032910

Montgomery, R. 2019. "Spanning trees in random graphs." Advances in Mathematics 356: 106793.
https://doi.org/10.1016/j.aim.2019.106793

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Kyriakos Katsamaktsis, Shoham Letzter, Amedeo Sgueglia

PDF