Packing trees of unbounded degrees in random graphs

Abstract

In this paper, we address the problem of packing large trees in $G_{n,p}$. In particular, we prove the following result. Suppose that $T_1,\dots ,T_N$ are $n$-vertex trees, each of which has maximum degree at most $(np{)}^{1/6}/(\log n{)}^6$. Then with high probability, one can find edge-disjoint copies of all the $T_i$ in the random graph $G_{n,p}$, provided that $p\ge (\log n{)}^{36}/n$ and $N\le (1-\epsilon )np/2$ for a positive constant $\epsilon$. Moreover, if each $T_i$ has at most $(1-\alpha )n$ vertices, for some positive $\alpha$, then the same result holds under the much weaker assumptions that $p\ge (\log n{)}^2/(cn)$ and $\Delta (T_i)\le cnp/\log n$ for some~$c$ that depends only on $\alpha$ and $\epsilon$. Our assumptions on maximum degrees of the trees are significantly weaker than those in all previously known approximate packing results.

References in corpus (4)

• Embedding bounded degree spanning trees in random graphs
• Packing minor-closed families of graphs into complete graphs
• Almost all trees are almost graceful
• A blow-up lemma for approximate decompositions

Cited by in corpus (4)

• Packing degenerate graphs
• Almost all trees are almost graceful
• Ringel's tree packing conjecture in quasirandom graphs
• The tree packing conjecture for trees of almost linear maximum degree