Limit theorems for complete subgraphs of random graphs
Limit theorems for complete subgraphs of random graphs
复制标题
随机图完全子图的极限定理
DOI：
10.1007/bf02018372
复制
发表时间：
1979
影响因子：
0.8
通讯作者：
K. Schürger
中科院分区：
文献类型：
--
作者：
K. Schürger
在续集中，所有考虑的图都是有限的，无向的，既没有环也没有多条边。我们研究定义如下的随机图I‘p~I’p(N)。I‘p(N)的顶点集为{1…，n}。每条可能的边以概率p-p(N)C[0，1]被选择，不同的边独立出现。~或许多问题这种类型的随机图(已经在[2]中提到；也比较[5]，[3])与随机选择边的数目N=N(N)的随机图之间没有本质区别，使得如果以这样的方式选择p(N)，则所有({2N)个可能的选择是相等的(见[2])；对于另一类随机图，比较[11]).如果F是一族图，记为PP{i‘p(N)6 F}，则PP(N)属于F的概率.我们研究大n的I’p(N)的性质.在这方面，我们感兴趣的是随机图的完全子图(子团)(如果图G的每一对顶点相邻，则称其为完全图).K-团是一个有k个顶点的完全图。用Zk(N)表示yP(N)的k-子曲线的个数。我们想指出的是，其中p不依赖于n的随机图的k-子团已在[6]、[7]和[9]中进行了研究。
In the sequel all graphs in consideration are finite, undirected and have neither loops nor multiple edges. We study the random graphs I'p~ I'p (n) being defined as follows. The set of vertices of I'p (n) is {1...., n}. Each possible edge is chosen with probability p-~ p (n) C [0, 1] and different edges occur independently.~ or many problems there is no essential difference between this type of random graphs (already mentioned in [2]; compare also [5],[3]) and that one in which a number N= N (n) of edges is chosen at random such that all ({2N)) possible choices are equiprobable if p (n) is chosen in such a way tha~ p (n){2)= N (n)(see [2]; for another type of random graphs compare [11]).If F is a family of graphs, denote by Pp {I'p (n) 6 F} the probability that Pp (n) belongs to F. We study the behaviour of I'p (n) for large n. In this context we~ re interested in complete subgraphs (subcliques) of random graphs (a graph G is called complete if G has every pair of its vertices adjacent). A k-clique is a complete graph with k vertices. Denote by zk (n) the number of k-subliques of Yp (n). We would like to mention that k-subcliques of random graphs in which p does not depend on n have been studied in [6],[7] and [9].