Fractional Clique Decompositions of Dense Graphs and Hypergraphs
arXiv:1507.04985 · doi:10.1016/j.jctb.2017.05.005
Abstract
Our main result is that every graph on vertices with minimum degree has a fractional -decomposition. Combining this result with recent work of Barber, Kühn, Lo and Osthus leads to the best known minimum degree thresholds for exact (non-fractional) -decompositions for a wide class of graphs~ (including large cliques). For general -uniform hypergraphs, we give a short argument which shows that there exists a constant such that every -uniform hypergraph on vertices with minimum codegree at least has a fractional -decomposition, where is the complete -uniform hypergraph on vertices. (Related fractional decomposition results for triangles have been obtained by Dross and for hypergraph cliques by Dukes as well as Yuster.) All the above new results involve purely combinatorial arguments. In particular, this yields a combinatorial proof of Wilson's theorem that every large -divisible complete graph has an -decomposition.
arXiv comment30 pages. To appear in Journal of Combinatorial Theory, Series B
References in corpus (5)
- The existence of designs
- Edge-decompositions of graphs with high minimum degree
- Clique decompositions of multipartite graphs and completion of Latin squares
- Asymptotically optimal -packings of dense graphs via fractional -decompositions
- Fractional triangle decompositions in graphs with large minimum degree
Cited by in corpus (6)
- Edge-decompositions of graphs with high minimum degree
- The existence of designs II
- Hypergraph -designs for arbitrary
- Packing degenerate graphs
- The existence of designs via iterative absorption: hypergraph -designs for arbitrary
- Clique decompositions of multipartite graphs and completion of Latin squares