Fractional clique decompositions of dense graphs and hypergraphs

Ben Barber, Daniela Kühn, Allan Lo, Richard Montgomery and Deryk Osthus, Journal of Combinatorial Theory, Series B, Volume 127, November 2017, Pages 148–186 PDF

Together with Daniela Kühn, Allan Lo and Deryk Osthus I proved that for every graph F there is a constant c_F < 1 such that every “F-divisible” graph G on n vertices with minimum degree at least (c_F + o(1))n has an F-decomposition. In practice, the current obstacle to improving the bounds on c_F is usually our knowledge of another quantity, the fractional decomposition threshold for cliques.

A graph G has a fractional F-decomposition if we can assign a non-negative weight to each copy of F in G such that the total weight of the copies of F containing each fixed edge of G is exactly 1. We prove that every graph with minimum degree at least (1-1/10000r^{3/2})n has a fractional K_r-decomposition. This greatly improves the previous bound of (1-2/9r^4)n for large r. We also prove a similar result for hypergraphs.

The proof begins with an approximate fractional K_r-decomposition obtained by weighting every r-clique in our graph equally. We then use small gadgets to make local adjustments to the total weight over each edge until we end up with a genuine fractional K_r-decomposition.

Leave a Reply

Your email address will not be published.