On Komlós’ tiling theorem in random graphs

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 ≥ Cn-1/m2(H), then asymptotically almost surely every spanning subgraph G of the random graph G (n, p) with minimum degree at least δ(G) ≥ (1 1/χcr(H) + γ)np contains an H-tiling that covers all but at most 3n 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 γ (C/p)m2(H) vertices, which is strictly smaller when p ≥ Cn- 1/{m2}(H). In the case where H = K3, 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. © 2019 Cambridge University Press.