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

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

A Note on Sharp Thresholds for Hamiltonicity in Random Intersection Graphs

The random intersection graph G （n,m,p） is deiined as tollows. Let V be a set of n nodes and M a set ot m elements. To each node v ∈ V , We assign a random subset Fv lohtain M , where Fv consists of elements in which each element is randomly and independently included with probability p from M. There is a edge between u and v if and only if Eu∩Fv≠Ф C. Efthymiou and P. G. Spirakis in [3] give sharp thresholds for the Hamilton cycle when re=n^a, where ct is different from 1. We get sharp threshold Pn= logn/n for Hamilton cycle when a = 1 using the second method. n