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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom