Scaling Limits of Random Graphs from Subcritical Classes
Scaling Limits of Random Graphs from Subcritical Classes
复制标题
亚临界类随机图的缩放限制
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Kerstin Weller
中科院分区：
文献类型：
--
作者：
K. Panagiotou;Benedikt Stufler;Kerstin Weller
我们研究均匀随机图 $mathsf{C}_n$ ，其中 $n$ 个顶点取自亚临界类连通图。我们的主要结果是，重新缩放的图 $mathsf{C}_n / sqrt{n}$ 收敛到布朗连续随机树 $mathcal{T}_{mathsf{e}}$ 乘以取决于所考虑的类的常数缩放因子。此外，我们还为有根随机图 $mathsf{C}_n^ ullet$ 的直径 $ext{D}(mathsf{C}_n)$ 和高度 $ext{H}(mathsf{C}_n^ ullet)$ 提供亚高斯尾界。我们给出了几个类别的比例因子的解析表达式，包括例如外平面图的突出类别。我们的方法还使我们能够研究 $mathsf{C}_n$ 上的第一代渗透，其中我们展示了在适当的重新缩放下到 $mathcal{T}_{mathsf{e}}$ 的收敛。
We study the uniform random graph $mathsf{C}_n$ with $n$ vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph $mathsf{C}_n / sqrt{n}$ converges to the Brownian Continuum Random Tree $mathcal{T}_{mathsf{e}}$ multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide subgaussian tail bounds for the diameter $ ext{D}(mathsf{C}_n)$ and height $ ext{H}(mathsf{C}_n^ullet)$ of the rooted random graph $mathsf{C}_n^ullet$. We give analytic expressions for the scaling factor of several classes, including for example the prominent class of outerplanar graphs. Our methods also enable us to study first passage percolation on $mathsf{C}_n$, where we show the convergence to $mathcal{T}_{mathsf{e}}$ under an appropriate rescaling.