Corrádi and Hajnal's theorem for sparse random graphs

József Balogh, Choongbum Lee, Wojciech Samotij

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)23-55
Number of pages33
JournalCombinatorics Probability and Computing
Issue number1-2
StatePublished - Jan 2012

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Corrádi and Hajnal's theorem for sparse random graphs'. Together they form a unique fingerprint.

Cite this