Families of trees decompose the random graph in any arbitrary way

2002/10/22 by Raphael Yuster, Yuster, Raphael
Mathematics · #05C80 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C80

paper · pdf · doi:10.48550/arxiv.math/0210339

20 pages

arxiv created 2002/10/22 · arxiv updated 2009/11/30

Abstract

Let F=\H₁,...,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 α₁ e(H₁) + ... + α_k e(H_k) = m where each α_i is a nonnegative integer, there is a coloring of the edges of G with α₁+...+α_k colors such that exactly α_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.

Related

• Decomposing almost complete graphs by random trees
• Sharp Thresholds for Factors in Random Graphs
• Packing tree factors in random and pseudo-random graphs
• Tree independence number V. Walls and claws
• On the decomposition threshold of a given graph