Packing tree factors in random and pseudo-random graphs (Q405193)

Summary: 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 \(\epsilon>0\), the random graph \(G_{n,p}\), with \(n\) a multiple of \(t\), with high probability contains a family of edge-disjoint \(T\)-factors covering all but an \(\epsilon\)-fraction of its edges, as long as \(\epsilon^4 n p \gg \log^2 n\). Assuming stronger divisibility conditions, the edge probability can be taken down to \(p>\frac{C\log n}{n}\). A similar packing result is proved also for pseudo-random graphs, defined in terms of their degrees and co-degrees.