Two critical periods in the evolution of random planar graphs
Two critical periods in the evolution of random planar graphs
复制标题
随机平面图演化的两个关键时期
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
T. Luczak
中科院分区：
文献类型：
--
作者：
Mihyun Kang;T. Luczak
设P（n;M）是从所有n个顶点M条边的标号平面图族中随机一致选取的图。本文研究了P（n;M）的分支结构。结合计数参数和分析技巧，我们证明了P（n;M）的演化存在两个临界期。第一个，宽度（n 2=3），类似于在标准随机图模型中观察到的相变，并发生在M = n=2 +O（n 2=3），当形成最大的复杂组件。当M = n + O（n3 =5）时，当复分量几乎覆盖所有顶点时，出现宽度为n3 =5的第二个临界周期.从那一刻开始，M的增加主要影响复杂组件的密度，而不是其大小。
Let P (n;M) be a graph chosen uniformly at random from the family of all labeled planar graphs with n vertices and M edges. In the paper we study the component structure of P (n;M). Combining counting arguments with analytic techniques, we show that there are two critical periods in the evolution of P (n;M). The first one, of width ( n 2=3 ), is analogous to the phase transition observed in the standard random graph models and takes place for M = n=2 +O(n 2=3 ), when the largest complex component is formed. Then, for M = n + O(n 3=5 ), when the complex components covers nearly all vertices, the second critical period of width n 3=5 occurs. Starting from that moment increasing of M mostly affects the density of the complex components, not its size.