Tree tilings in random regular graphs

2024/12/27 by Diskin, Sahar, Hoshen, Ilay, Zhukovskii, Maksim
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2412.19756

Abstract

We show that for every ε>0 there exists a sufficiently large d₀∈ ℕ such that for every d≥ d₀, whp the random d-regular graph G(n,d) contains a T-factor for every tree T on at most (1-ε)d/ln d vertices. This is best possible since, for large enough integer d, whp G(n,d) does not contain a ((1+ε)d)/(ln d)-star-factor. Our method gives a randomised algorithm which whp finds said T-factor and whose expected running time is O(n^1+o(1)), as well as an efficient deterministic counterpart.

Related

• Packing tree factors in random and pseudo-random graphs
• Tilings in quasi-random k-partite hypergraphs
• Decomposing random regular graphs into stars
• Tilings in randomly perturbed graphs: bridging the gap between Hajnal-Szemerédi and Johansson-Kahn-Vu
• Tilings in randomly perturbed dense graphs