Fractional clique decompositions of dense graphs and hypergraphs

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

Research output: Contribution to journalArticle (Academic Journal)peer-review

9 Citations (Scopus)
114 Downloads (Pure)

Abstract

Our main result is that every graph G on n≥104r3 vertices with minimum degree δ(G)≥(1−1/104r3/2)n has a fractional Kr-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) F-decompositions for a wide class of graphs F (including large cliques). For general k-uniform hypergraphs, we give a short argument which shows that there exists a constant ck>0 such that every k-uniform hypergraph G on n vertices with minimum codegree at least (1−ck/r2k−1)n has a fractional Kr(k)-decomposition, where Kr(k) is the complete k-uniform hypergraph on r 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 F-divisible complete graph has an F-decomposition.
Original languageEnglish
Pages (from-to)148-186
Number of pages29
JournalJournal of Combinatorial Theory Series B
Volume127
Early online date2 Jun 2017
DOIs
Publication statusPublished - 1 Nov 2017

Keywords

  • Fractional decomposition
  • Minimum degree
  • Cliques

Fingerprint

Dive into the research topics of 'Fractional clique decompositions of dense graphs and hypergraphs'. Together they form a unique fingerprint.

Cite this