On Komlós’ tiling theorem in random graphs

Source abstract

Abstract Given graphs G and H , a family of vertex-disjoint copies of H in G is called an H-tiling . Conlon, Gowers, Samotij and Schacht showed that for a given graph H and a constant γ >0 , there exists C >0 such that if $p \ge C{n^{ - 1/{m_2}(H)}}$ , then asymptotically almost surely every spanning subgraph G of the random graph 𝒢 ( n, p ) with minimum degree at least $\delta (G) \ge (1 - \frac{1}{{{\chi _{{\rm{cr}}}}(H)}} + \gamma )np$ contains an H -tiling that covers all but at most γn vertices. Here, χ cr( H ) denotes the critical chromatic number , a parameter introduced by Komlós, and m 2 ( H ) is the 2 -density of H . We show that this theorem can be bootstrapped to obtain an H -tiling covering all but at most $\gamma {(C/p)^{{m_2}(H)}}$ vertices, which is strictly smaller when $p \ge C{n^{ - 1/{m_2}(H)}}$ . In the case where H = K 3 , this answers the question of Balogh, Lee and Samotij. Furthermore, for an arbitrary graph H we give an upper bound on p for which some leftover is unavoidable and a bound on the size of a largest H -tiling for p below this value.