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

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

2010-11-24

arxiv.org/abs/1011.5443v2

Mathematics

Combinatorics

Scientific paper

In this paper we extend a classical theorem of Corr\'adi and Hajnal into the setting of sparse random graphs. We show that if $p(n) \gg (\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.

Affiliated with

Also associated with

No associations

Rating

Corrádi and Hajnal's theorem for sparse random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Corrádi and Hajnal's theorem for sparse random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Corrádi and Hajnal's theorem for sparse random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-241541