Spanning Subgraphs of Random Graphs
Spanning Subgraphs of Random Graphs
复制标题
随机图的生成子图
DOI：
10.1017/s0963548399004150
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
O. Riordan
中科院分区：
文献类型：
--
作者：
O. Riordan
设Gp是2d个顶点上的随机图，其中边以固定概率p > 1/4独立选择，并且设H是d维超立方体Qd。我们回答了Bollobás的一个问题，证明了当d → ∞时，Gp几乎必然有一个生成子图同构于H。事实上，我们证明了一个更强的结果，即G ∈ [Gscr ]（n，M）中的d-立方数对M在一定范围内是渐近正态分布的.所得结果可推广到其它许多图，也改进了以前关于格点即二维正方形格点的结果。证明使用二阶矩方法-写X为G的同构于H的子图的数目，其中G是合适的随机图，我们将X的方差展开为H本身的所有子图的和。由于H的子图可能相当复杂，大部分工作是估计这个和的各项。
Let Gp be a random graph on 2d vertices where edges are selected independently with a fixed probability p > ¼, and let H be the d-dimensional hypercube Qd. We answer a question of Bollobás by showing that, as d → ∞, Gp almost surely has a spanning subgraph isomorphic to H. In fact we prove a stronger result which implies that the number of d-cubes in G ∈ [Gscr ](n, M) is asymptotically normally distributed for M in a certain range. The result proved can be applied to many other graphs, also improving previous results for the lattice, that is, the 2-dimensional square grid. The proof uses the second moment method – writing X for the number of subgraphs of G isomorphic to H, where G is a suitable random graph, we expand the variance of X as a sum over all subgraphs of H itself. As the subgraphs of H may be quite complicated, most of the work is in estimating the various terms of this sum.