2013/04/08 by Deepak Bal, Alan Frieze, Bal, Deepak +5
Mathematics · #05C05 #05C70 #05C80 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C05 #msc:05C70 #msc:05C80
paper · pdf · doi:10.48550/arxiv.1304.2429
12 pages
arxiv created 2014/04/01 · arxiv updated 2014/04/02
For a fixed graph H with t vertices, an H-factor of a graph G with n vertices, where t divides n, is a collection of vertex disjoint (not necessarily induced) copies of H in G covering all vertices of G. We prove that for a fixed tree T on t vertices and ε> 0, the random graph Gn,p, with n a multiple of t, with high probability contains a family of edge-disjoint T-factors covering all but an ε-fraction of its edges, as long as ε4 n p >> (log n)2. Assuming stronger divisibility conditions, the edge probability can be taken down to p > (C log n)/n. A similar packing result is proved also for pseudo-random graphs, defined in terms of their degrees and co-degrees.