Ben Barber, Daniela Kühn, Allan Lo, Richard Montgomery and Deryk Osthus, Journal of Combinatorial Theory, Series B 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.