Edge-decompositions of graphs with high minimum degree

Abstract

A fundamental theorem of Wilson states that, for every graph $F$, every sufficiently large $F$-divisible clique has an $F$-decomposition. Here a graph $G$ is $F$-divisible if $e(F)$ divides $e(G)$ and the greatest common divisor of the degrees of $F$ divides the greatest common divisor of the degrees of $G$, and $G$ has an $F$-decomposition if the edges of $G$ can be covered by edge-disjoint copies of $F$. We extend this result to graphs $G$ which are allowed to be far from complete. In particular, together with a result of Dross, our results imply that every sufficiently large $K_3$-divisible graph of minimum degree at least $9n/10+o(n)$ has a $K_3$-decomposition. This significantly improves previous results towards the long-standing conjecture of Nash-Williams that every sufficiently large $K_3$-divisible graph with minimum degree at least $3n/4$ has a $K_3$-decomposition. We also obtain the asymptotically correct minimum degree thresholds of $2n/3+o(n)$ for the existence of a $C_4$-decomposition, and of $n/2+o(n)$ for the existence of a $C_{2\ell }$-decomposition, where $\ell \ge 3$. Our main contribution is a general `iterative absorption' method which turns an approximate or fractional decomposition into an exact one. In particular, our results imply that in order to prove an asymptotic version of Nash-Williams' conjecture, it suffices to show that every $K_3$-divisible graph with minimum degree at least $3n/4+o(n)$ has an approximate $K_3$-decomposition,

41 pages. This version includes some minor corrections, updates and improvements

References in corpus (5)

• The existence of designs
• Fractional Clique Decompositions of Dense Graphs and Hypergraphs
• Clique decompositions of multipartite graphs and completion of Latin squares
• Asymptotically optimal $K_k$-packings of dense graphs via fractional $K_k$-decompositions
• Fractional triangle decompositions in graphs with large minimum degree

Cited by in corpus (17)

• The existence of designs II
• Fractional Clique Decompositions of Dense Graphs and Hypergraphs
• Hypergraph $F$-designs for arbitrary $F$
• The existence of designs via iterative absorption: hypergraph $F$-designs for arbitrary $F$
• Bounds on Separating Redundancy of Linear Codes and Rates of X-Codes
• Clique decompositions of multipartite graphs and completion of Latin squares
• Ramsey numbers of bounded degree trees versus general graphs
• A blow-up lemma for approximate decompositions
• Countable homogeneous Steiner triple systems avoiding specified subsystems
• Fractional triangle decompositions in graphs with large minimum degree
• Fractional triangle decompositions in almost complete graphs
• Counting spanning subgraphs in dense hypergraphs
• Monochromatic triangle packings in red-blue graphs
• The $n$-queens problem
• Cycle decompositions in $k$-uniform hypergraphs
• The combinatorial game nofil played on Steiner Triple Systems
• On the cone of weighted graphs generated by triangles