Premium
Factors in random graphs
Author(s) -
Johansson Anders,
Kahn Jeff,
Vu Van
Publication year - 2008
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.20224
Subject(s) - combinatorics , corollary , hypergraph , mathematics , random regular graph , vertex (graph theory) , random graph , discrete mathematics , partition (number theory) , graph , line graph , 1 planar graph
Let H be a fixed graph on v vertices. For an n ‐vertex graph G with n divisible by v , an H ‐factor of G is a collection of n / v copies of H whose vertex sets partition V ( G ). In this work, we consider the threshold t h H ( n ) of the property that an Erdős‐Rényi random graph (on n points) contains an H ‐factor. Our results determine t h H ( n ) for all strictly balanced H . The method here extends with no difficulty to hypergraphs. As a corollary, we obtain the threshold for a perfect matching in random k ‐uniform hypergraph, solving the well‐known “Shamir's problem.” © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008
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