On the decomposition threshold of a given graph

Abstract

We study the $F$-decomposition threshold ${\delta }_F$ for a given graph $F$. Here an $F$-decomposition of a graph $G$ is a collection of edge-disjoint copies of $F$ in $G$ which together cover every edge of $G$. (Such an $F$-decomposition can only exist if $G$ is $F$-divisible, i.e. if $e(F)\mid e(G)$ and each vertex degree of $G$ can be expressed as a linear combination of the vertex degrees of $F$.) The $F$-decomposition threshold ${\delta }_F$ is the smallest value ensuring that an $F$-divisible graph $G$ on $n$ vertices with $\delta (G)\ge ({\delta }_F+o(1))n$ has an $F$-decomposition. Our main results imply the following for a given graph $F$, where ${\delta }_F^{\ast }$ is the fractional version of ${\delta }_F$ and $\chi :=\chi (F)$: (i) ${\delta }_F\le \max \{{\delta }_F^{\ast },1-1/(\chi +1)\}$; (ii) if $\chi \ge 5$, then ${\delta }_F\in \{{\delta }_F^{\ast },1-1/\chi ,1-1/(\chi +1)\}$; (iii) we determine ${\delta }_F$ if $F$ is bipartite. In particular, (i) implies that ${\delta }_{K_r}={\delta }_{K_r}^{\ast }$. Our proof involves further developments of the recent `iterative' absorbing approach.

Final version, to appear in the Journal of Combinatorial Theory, Series B