次临界随机相交图的最大连通分支

The largest component of the random intersection graph in the subcritical regime

本文研究次临界情形下(即顶点度数的期望小于1)随机相交图G(n,m,p)的最大连通分支的大小.设m=[n^(r)].当r>1时,随机相交图G(n,m,p)的最大连通分支和最大树分支大小都为Θ(log n),并具有相同形式的弱大数定律;当r=1时,最大连通分支不再是树分支,但最大连通分支和最大树分支的大小也是Θ(log n);当0<r<1时,最大树分支的大小为o(log n),而最大连通分支的大小为Θ(np log n).

We study the size of the largest component of the random intersection graph G(n,m,p)with m=[nr]in the subcritical regime,i.e.,the case where the expected vertex degree is smaller than one.If r 1,then the largest component and the largest tree component have the same type of the weak law of large numbers,and both of them are of orderΘ(log n);if r=1,then the largest component is not a tree,but the largest component and the largest tree component are also of orderΘ(log n);if 0 r 1,then the largest tree component is of order o(log n)while the largest component is of orderΘ(np log n).