Triangle factors of graphs without large independent sets and of weighted graphs1. Issue 4 (23rd August 2016)

• Record Type: Journal Article
• Authors: Balogh, József; Molla, Theodore; Sharifzadeh, Maryam
• Is Part Of: Random structures & algorithms. Volume 49:Issue 4(2016)
• Page Start: 669
• Page End: 693
• Publication Date: 2016-08-23
• Subjects: extremal problems -- factorization -- matching, partitioning, covering and packing -- probabilistic methods; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20670
• Languages: English
• ISSNs: 1042-9832

Abstract

ABSTRACT: The classical Corrádi‐Hajnal theorem claims that every n ‐vertex graph G with δ ( G ) ≥ 2 n / 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 ) = o ( 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 3 t . 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 + 2 t 3 + o ( 1 ) ) n, then there are n / 3 vertex disjoint heavy triangles in G . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 669–693, 2016