On Komlós' tiling theorem in random graphs

Abstract

Conlon, Gowers, Samotij, and Schacht showed that for a given graph $H$ and a constant $\gamma >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 $\mathcal{G}(n,p)$ with minimum degree at least $\delta (G)\ge (1-1/{\chi }_{\mathrm{cr}}(H)+\gamma )np$ contains an $H$-packing that covers all but at most $\gamma n$ vertices. Here, ${\chi }_{\mathrm{cr}}(H)$ denotes the critical chromatic threshold, a parameter introduced by Komlós. We show that this theorem can be bootstraped to obtain an $H$-packing covering all but at most $\gamma (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$.