Fractional clique decompositions of dense graphs and hypergraphs

Ben Barber, Daniela Kühn, Allan Lo, Richard Montgomery and Deryk Osthus PDF

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

A graph has a fractional -decomposition if we can assign a non-negative weight to each copy of in such that the total weight of the copies of containing each fixed edge of is exactly 1. We prove that every graph with minimum degree at least has a fractional -decomposition. This greatly improves the previous bound of for large . We also prove a similar result for hypergraphs.

The proof begins with an approximate fractional -decomposition obtained by weighting every -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 -decomposition.

Leave a Reply

Your email address will not be published.