The continuum limit of critical random graphs
The continuum limit of critical random graphs
复制标题
DOI：
10.1007/s00440-010-0325-4
复制
发表时间：
2009-03
影响因子：
2
通讯作者：
L. Addario-Berry;N. Broutin;C. Goldschmidt
中科院分区：
文献类型：
--
作者：
L. Addario-Berry;N. Broutin;C. Goldschmidt
我们考虑临界窗口内的 Erdős–Rényi 随机图 G(n,p)，即当 p= 1/n+ λn−4/3 时，对于某些固定值。我们证明 G(n,p) 的连通分量序列（使用按 n−1/3 重新缩放的图距离视为度量空间）收敛于连续紧度量空间序列。结果依赖于图和某些标记随机游走之间的双射，以及连续随机树理论。我们的结果提供了有关关键随机图中距离的许多问题的答案。特别是，我们推断出 G(n,p) 的直径按 n−1/3 重新调整后在分布中收敛为具有有限均值的绝对连续随机变量。
We consider the Erdős–Rényi random graphG(n,p) inside the critical window, that is whenp= 1/n+ λn−4/3, for some fixed. We prove that the sequence of connected components ofG(n,p), considered as metric spaces using the graph distance rescaled byn−1/3, converges towards a sequence of continuous compact metric spaces. The result relies on a bijection between graphs and certain marked random walks, and the theory of continuum random trees. Our result gives access to the answers to a great many questions about distances in critical random graphs. In particular, we deduce that the diameter ofG(n,p) rescaled byn−1/3converges in distribution to an absolutely continuous random variable with finite mean.