Limits of randomly grown graph sequences
Limits of randomly grown graph sequences
复制标题
随机生长图序列的限制
DOI：
10.1016/j.ejc.2011.03.015
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
K. Vesztergombi
中科院分区：
文献类型：
--
作者：
C. Borgs;J. Chayes;L. Lovász;V. Sós;K. Vesztergombi
Borgs、Chayes、Lovász、S、S、Szegedy和Vesztergombi部分受到在随机规则(如互联网模型)下生长的各种图序列的启发，引入了稠密图的收敛序列及其极限。在本文中，我们使用这个框架来研究一类具有激励作用的例子，即随机增长图。我们证明了几个这样的随机增长图序列的(几乎必然)收敛，并确定了它们的极限。分析并不总是直截了当的：在某些情况下，可以直接估计到极限对象的割距离，而在其他情况下，子图的密度可以被证明是收敛的。
Motivated in part by various sequences of graphs growing under random rules (such as Internet models), Borgs, Chayes, Lovász, Sós, Szegedy and Vesztergombi introduced convergent sequences of dense graphs and their limits. In this paper we use this framework to study one of the motivating classes of examples, namely randomly growing graphs. We prove the (almost sure) convergence of several such randomly growing graph sequences, and determine their limit. The analysis is not always straightforward: in some cases the cut-distance from a limit object can be directly estimated, while in other cases densities of subgraphs can be shown to converge.