Families of trees decompose the random graph in any arbitrary way

Abstract

Let $F=\{H_1,...,H_k\}$ be a family of graphs. A graph $G$ with $m$ edges is called {\em totally $F$-decomposable} if for {\em every} linear combination of the form ${\alpha }_{1}e(H_1)+...+{\alpha }_{k}e(H_k)=m$ where each ${\alpha }_i$ is a nonnegative integer, there is a coloring of the edges of $G$ with ${\alpha }_1+...+{\alpha }_k$ colors such that exactly ${\alpha }_i$ color classes induce each a copy of $H_i$, for $i=1,...,k$. We prove that if $F$ is any fixed family of trees then $\log n/n$ is a sharp threshold function for the property that the random graph $G(n,p)$ is totally $F$-decomposable. In particular, if $H$ is a tree, then $\log n/n$ is a sharp threshold function for the property that $G(n,p)$ contains $\lfloor e(G)/e(H)\rfloor$ edge-disjoint copies of $H$.

20 pages