## Abstract

The classical Corrádi-Hajnal theorem claims that every n-vertex graph G with δ(G)≥2n/3 contains a triangle factor, when 3|n. In this paper we present two related results that both use the absorbing technique of Rödl, Ruciński and Szemerédi. Our main result determines the minimum degree condition necessary to guarantee a triangle factor in graphs with sublinear independence number. In particular, we show that if G is an n-vertex graph with α(G) = on(n) and δ(G) ≥(1/2 + o(1))n, then G has a triangle factor and this is asymptotically best possible. Furthermore, it is shown for every r that if every linear size vertex set of a graph G spans quadratically many edges, and δ(G) ≥(1/2 + o(1))n, then G has a K_{r}-factor for n sufficiently large. We also propose many related open problems whose solutions could show a relationship with Ramsey-Turán theory. Additionally, we also consider a fractional variant of the Corrádi-Hajnal Theorem, settling a conjecture of Balogh-Kemkes-Lee-Young. Let t є (0,1) and w : E(K_{n}) → [0,1]. We call a triangle t-heavy if the sum of the weights on its edges is more than 3t. We prove that if 3|n and w is such that for every vertex v the sum of w(e) over edges e incident to v is at least (1+2t/3 + o(1))n, then there are n/3 vertex disjoint heavy triangles in G.

Original language | English (US) |
---|---|

Pages (from-to) | 669-693 |

Number of pages | 25 |

Journal | Random Structures and Algorithms |

Volume | 49 |

Issue number | 4 |

DOIs | |

State | Published - Dec 1 2016 |

## Keywords

- extremal problems
- factorization
- matching, partitioning, covering and packing
- probabilistic methods

## ASJC Scopus subject areas

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics