2016/11/29 by Nenadov, Rajko, Škorić, Nemanja
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1611.09466
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-packing that covers all but at most γn vertices. Here, χ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 γ(C/p)m2(H) vertices, which is strictly smaller when p > C n-1/m2(H). In the case where H = K3 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.