随机图中的K_4-因子

K_4-factors in random graphs

设图G具有n个顶点,图的K_4-因子是由■个顶点互不相交的K_4构成的图G的子图(其中4整除n)。我们试图寻找尽可能小的概率使得随机图G几乎必然包含K_4-因子。应用概率方法,给出当概率p=O(n^(-0.44))时,随机图G(n,p)几乎必然包含K_4-因子。

For a graph G with n vertices,where 4 divides n,a K4-factor is a subgraph of G,consisting of n/4 vertex disjoint K4.The minimal probability p=p(n)for which a random graph G(n,p)almost surely contains a K4-factor.For p=O(n^-0.44),the random graph G(n,p)almost surely contains a K4-factor.