Fractional clique decompositions of dense graphs

2017/11/09 by Montgomery, Richard · 7 citations
#05C70 #05C72 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1711.03382

Abstract

For each r≥ 4, we show that any graph G with minimum degree at least (1-1/100r)|G| has a fractional K_r-decomposition. This improves the best previous bounds on the minimum degree required to guarantee a fractional K_r-decomposition given by Dukes (for small r) and Barber, Kühn, Lo, Montgomery and Osthus (for large r), giving the first bound that is tight up to the constant multiple of r (seen, for example, by considering Turán graphs). In combination with work by Glock, Kühn, Lo, Montgomery and Osthus, this shows that, for any graph F with chromatic number χ(F)≥ 4, and any ε>0, any sufficiently large graph G with minimum degree at least (1-1/100χ(F)+ε)|G| has, subject to some further simple necessary divisibility conditions, an (exact) F-decomposition.

Cited by

• On the Hypergraph Nash-Williams' Conjecture
• Maximal sets of mutually orthogonal frequency squares and Doehlert-Klee designs
• Refined Absorption: A New Proof of the Existence Conjecture and its Applications to Extremal and Probabilistic Design Theory
• Progress towards generalized Nash-Williams' conjecture on K₄-decompositions
• Fractional Clique Decompositions of Dense Hypergraphs
• Beyond Nash-Williams: Counterexamples to Clique Decomposition Thresholds for All Cliques Larger than Triangles
• Erdős meets Nash-Williams

Related

• Fractional Clique Decompositions of Dense Partite Graphs
• Fractional Clique Decompositions of Dense Hypergraphs
• Progress towards generalized Nash-Williams' conjecture on K₄-decompositions
• Fractional triangle decompositions in graphs with large minimum degree
• Beyond Nash-Williams: Counterexamples to Clique Decomposition Thresholds for All Cliques Larger than Triangles