Packing random graphs and hypergraphs

We determine to within a constant factor the threshold for the property that two random k‐uniform hypergraphs with edge probability p have an edge‐disjoint packing into the same vertex set. More generally, we allow the hypergraphs to have different densities. In the graph case, we prove a stronger r...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2017-08, Vol.51 (1), p.3-13
Main Authors: Bollobás, Béla, Janson, Svante, Scott, Alex
Format: Article
Language:English
Subjects:
Graph theory
Graphs
packing
random hypergraphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We determine to within a constant factor the threshold for the property that two random k‐uniform hypergraphs with edge probability p have an edge‐disjoint packing into the same vertex set. More generally, we allow the hypergraphs to have different densities. In the graph case, we prove a stronger result, on packing a random graph with a fixed graph. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 3–13, 2017
ISSN:1042-9832
1098-2418
1098-2418
DOI:10.1002/rsa.20673