Families of trees decompose the random graph in any arbitrary way

Original · EN

Let F={H₁,...,Hₖ} be a family of graphs. A graph G with m edges is called totally F-decomposable if for every linear combination of the form α₁ e(H₁) +... + αₖ e(Hₖ) = m where each αᵢ is a nonnegative integer, there is a coloring of the edges of G with α₁+...+αₖ colors such that exactly αᵢ color classes induce each a copy of Hᵢ, for i=1,...,k. We prove that if F is any fixed family of trees then 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 n/n is a sharp threshold function for the property that G(n,p) contains e(G)/e(H) edge-disjoint copies of H.