关于随机相交图中Hamilton圈的门限函数的注记

摘要

随机相交图G(n,m,P)的定义如下:记V为-n顶点集.M为-m个元素的集合.对每个顶点v∈V,赋予一随机子集Fv(C)M,其中从M中独立以概率P选取每个元素构成Fv,顶点u和v之间有边相连当且仅当Fu∩Fv≠Φ.当m=na,a≠1时.C.Efthymiou和P.G.Spirakis得到了G(n,m,P)中Hamilton圈的门限函数.对于a=1情形,本文利用二阶矩方法(Chebyshev不等式)得到了类似结果.