Premium
Packing random graphs and hypergraphs
Author(s) -
Bollobás Béla,
Janson Svante,
Scott Alex
Publication year - 2017
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20673
Subject(s) - combinatorics , random graph , mathematics , random regular graph , hypergraph , disjoint sets , vertex (graph theory) , struct , graph , discrete mathematics , enhanced data rates for gsm evolution , line graph , computer science , 1 planar graph , telecommunications , programming language
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