On the decomposition threshold of a given graph


Abstract in English

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_Fle max{delta_F^ast,1-1/(chi+1)}$; (ii) if $chige 5$, then $delta_Fin{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^ast_{K_r}$. Our proof involves further developments of the recent `iterative absorbing approach.

Download