Corrádi and Hajnal's Theorem for Sparse Random Graphs

Source abstract

In this paper we extend a classical theorem of Corrádi and Hajnal into the setting of sparse random graphs. We show that if p ( n ) ≫ (log n / n ) 1/2 , then asymptotically almost surely every subgraph of G ( n , p ) with minimum degree at least (2/3 + o (1)) np contains a triangle packing that covers all but at most O ( p −2 ) vertices. Moreover, the assumption on p is optimal up to the (log n ) 1/2 factor and the presence of the set of O ( p −2 ) uncovered vertices is indispensable. The main ingredient in the proof, which might be of independent interest, is an embedding theorem which says that if one imposes certain natural regularity conditions on all three pairs in a balanced 3-partite graph, then this graph contains a perfect triangle packing.