On Komlós' tiling theorem in random graphs

Abstract: Conlon, Gowers, Samotij, and Schacht showed that for a given graph

H

and a constant

g a m m a > 0

, there exists

C > 0

such that if

p g e C n^{- 1 / m_{2} (H)}

then asymptotically almost surely every spanning subgraph

G

of the random graph

m a t h c a l G (n, p)

with minimum degree at least

d e l t a (G) g e (1 - 1 / c h i_{m a t h r m c r} (H) + g a m m a) n p

contains an

H

-packing that covers all but at most

g a m m a n

vertices. Here,

c h i_{m a t h r m c r} (H)

denotes the critical chromatic threshold, a parameter introduced by Koml'os. We show that this theorem can be bootstraped to obtain an

H

-packing covering all but at most

g a m m a (C / p)^{m_{2} (H)}

vertices, which is strictly smaller when

p > C n^{- 1 / m_{2} (H)}

. In the case where

H = K_{3}

this answers the question of Balogh, Lee, and Samotij. Furthermore, we give an upper bound on the size of an

H

-packing for certain ranges of

p

.

Recommendations

Cites Work

Cited In (8)

This page was built for publication: On Komlós' tiling theorem in random graphs