2010/11/24 by József Balogh, Balogh, József, Choongbum Lee +3
Computer Science · Mathematics · #05C35 #05C70 #05C80 #05D40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1011.5443
openalex publication_date 2010/11/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.