标题： 无界度数的树在随机图中的打包 显示英文标题

标题： Packing trees of unbounded degrees in random graphs

摘要： 在本文中，我们研究了在$G_{n,p}$中打包大型树的问题。 特别是，我们证明了以下结果。 假设$T_1, \dotsc, T_N$是$n$顶点的树，每棵树的最大度数至多为$(np)^{1/6} / (\log n)^6$。 然后在高概率下，可以找到所有边不相交的$T_i$在随机图$G_{n,p}$中，前提是$p \geq (\log n)^{36}/n$和$N \le (1-\varepsilon)np/2$对于一个正数常量$\varepsilon$。 此外，如果每个 $T_i$ 至多有 $(1-\alpha)n$个顶点，对于某个正数 $\alpha$，那么在更弱的假设下同样的结果仍然成立，即 $p \geq (\log n)^2/(cn)$ 和 $\Delta(T_i) \leq c np / \log n$ 对于某个仅依赖于 $\alpha$ 和 $\varepsilon$ 的 $c$ 而言。 我们对树的最大度数的假设比所有先前已知的近似装填结果中的假设要弱得多。 显示英文摘要

摘要： 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, \dotsc, 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 \geq (\log n)^{36}/n$ and $N \le (1-\varepsilon)np/2$ for a positive constant $\varepsilon$. 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 \geq (\log n)^2/(cn)$ and $\Delta(T_i) \leq c np / \log n$ for some~$c$ that depends only on $\alpha$ and $\varepsilon$. Our assumptions on maximum degrees of the trees are significantly weaker than those in all previously known approximate packing results.