Combinatorics, Probability and Computing

Table of Contents - March 2012 - Volume 21, Special Issue 1-2 (Honouring the Memory of Richard H. Schelp)  

Paper

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

JÓZSEF BALOGHa1†, CHOONGBUM LEEa2‡ and WOJCIECH SAMOTIJa3§

a1 Department of Mathematics, University of Illinois, 1409 W Green Street, Urbana, IL 61801, USA and Department of Mathematics, University of California, San Diego, CA 92093, USA (e-mail: jobal@math.uiuc.edu)

a2 Department of Mathematics, UCLA, Los Angeles, CA 90095, USA (e-mail: choongbum.lee@gmail.com)

a3 School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Trinity College, Cambridge CB2 1TQ, UK (e-mail: samotij@post.tau.ac.il)

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.

(Received November 24 2010)

(Revised November 01 2011)

(Online publication February 02 2012)

Footnotes

† This material is based upon work supported by NSF CAREER Grant DMS-0745185 and OTKA Grant K76099.

‡ Research supported in part by a Samsung Scholarship.

§ Research supported in part by ERC Advanced Grant DMMCA.