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