N叉树上的可达渗流

考虑一棵有根的N叉树,赋予此树的每个顶点一个独立同分布的连续随机变量。如果从根点到某个顶点路径上的随机变量是递增的,我们就称这个顶点是可到达的。考虑在N叉树中前k层可到达顶点的数目C_(N,k)和可到达顶点的总数目C_(N),当N→∞时,得到了C_(N,βN)不同的极限分布(随着β从0到+∞变化),建立了C_(N)的极限性质。当N固定时,也考虑了N叉树中前n层最长递增路径长度的大数定律。

The Number of Triangles in Random Intersection Graphs

Let Tn be the number of triangles in the random intersection graph G(n,m,p).When the mean of Tn is bounded,we obtain an upper bound on the total variation distance between Tn and a Poisson distribution.When the mean of Tn tends to infinity,the Stein–Tikhomirov method is used to bound the error for the normal approximation of Tn with respect to the Kolmogorov metric.

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

本文研究次临界情形下(即顶点度数的期望小于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).

Number of edges in inhomogeneous random graphs

We study the number of edges in the inhomogeneous random graph when vertex weights have an infinite mean and show that the number of edges is O(n log n).Central limit theorems for the number of edges are also established.