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}, d o t s c, T_{N}

are

n

-vertex trees, each of which has maximum degree at most

(n p)^{1 / 6} / (l o g 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 g e q (l o g n)^{36} / n

and

N l e (1 - v a r e p s i l o n) n p / 2

for a positive constant

v a r e p s i l o n

. Moreover, if each

T_{i}

has at most

(1 - a l p h a) n

vertices, for some positive

a l p h a

, then the same result holds under the much weaker assumptions that

p g e q (l o g n)^{2} / (c n)

and

D e l t a (T_{i}) l e q c n p / l o g n

for some~

c

that depends only on

a l p h a

and

v a r e p s i l o n

. Our assumptions on maximum degrees of the trees are significantly weaker than those in all previously known approximate packing results.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Packing trees of unbounded degrees in random graphs