Packing tree factors in random and pseudo-random graphs

Authors Deepak Bal, Michael Krivelevich, Po-Shen Loh, Alan Frieze

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.2429, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p8

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

packing pseudo-random graphs random graphs tree factors

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Abstract: 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 >> (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.

Review text

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.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Packing tree factors in random and pseudo-random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405193)