Subgraphs of Dense Random Graphs with Specified Degrees
Subgraphs of Dense Random Graphs with Specified Degrees
复制标题
指定次数的密集随机图的子图
DOI：
10.1017/s0963548311000034
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
B. McKay
中科院分区：
文献类型：
--
作者：
B. McKay
令 d = (d1, d2, ..., dn) 为具有偶数和的非负整数向量。我们证明了关于度数序列为 d 的随机图结构的一些基本事实，包括给定子图或导出子图的概率。尽管此类结果有很多，但它们仅限于稀疏情况，只有少数例外。我们的重点是平均度数近似为 n 的常数分数的情况。我们的方法是多维鞍点法。这扩展了 McKay 和 Wormald (1990) 的枚举工作，并且类似于 Greenhill 和 McKay (2009) 为二分图开发的理论。
Let d = (d1, d2, . . ., dn) be a vector of non-negative integers with even sum. We prove some basic facts about the structure of a random graph with degree sequence d, including the probability of a given subgraph or induced subgraph. Although there are many results of this kind, they are restricted to the sparse case with only a few exceptions. Our focus is instead on the case where the average degree is approximately a constant fraction of n. Our approach is the multidimensional saddle-point method. This extends the enumerative work of McKay and Wormald (1990) and is analogous to the theory developed for bipartite graphs by Greenhill and McKay (2009).