Some Large Deviation Results for Sparse Random Graphs
Some Large Deviation Results for Sparse Random Graphs
复制标题
稀疏随机图的一些大偏差结果
DOI：
10.1016/j.ejc.2006.05.006
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
J. F.
中科院分区：
文献类型：
--
作者：
J. F.
我们获得了具有小边缘概率的随机图中最大连通分量的相对大小的大偏差原理（LDP）。速率函数通常不是凸的，它是使用新技术明确确定的。作为推论，我们提出了随机图连通概率的渐近公式。我们还提供了 LDP 和孤立顶点数量的相关结果。在这里，我们利用了一个简单但显然未知的特征，它是通过将随机图嵌入到随机有向图中而获得的。结果表明，在这种缩放下，属性“连接”和“不包含孤立顶点”不是渐近等价的。 （在阈值概率下它们是渐近等价的。）
We obtain a large deviation principle (LDP) for the relative size of the largest connected component in a random graph with small edge probability. The rate function, which is not convex in general, is determined explicitly using a new technique. As a corollary we present an asymptotic formula for the probability that the random graph is connected. We also present an LDP and related result for the number of isolated vertices. Here we make use of a simple but apparently unknown characterisation, which is obtained by embedding the random graph in a random directed graph. The results demonstrate that, at this scaling, the properties 'connected' and 'contains no isolated vertices' are not asymptotically equivalent. (At the threshold probability they are asymptotically equivalent.)