Threshold Functions for H -factors
Noga Alon, Raphael Yuster · Combinatorics Probability Computing · 1993
Let H be a graph on h vertices, and G be a graph on n vertices. An H-factor of G is a spanning subgraph of G consisting of n/h vertex disjoint copies of H . The fractional arboricity of H is , where the maximum is taken over all subgraphs ( V ′, E′) of H with | V′ | > 1. Let δ( H ) denote the minimum degree of a vertex of H . It is shown that if δ( H ) < a ( H ), then n −1/ a ( H ) is a sharp threshold function for the property that the random graph G ( n, p ) contains an H -factor. That is, there are two positive constants c and C so that for p ( n ) = cn −1/ a ( H ) almost surely G ( n, p ( n )) does not have an H -factor, whereas for p ( n ) = Cn −1/ a ( H ), almost surely G ( n, p ( n )) contains an H -factor (provided h divides n ). A special case of this answers a problem of Erdős.