Percolation in General Graphs
Percolation in General Graphs
复制标题
一般图中的渗透
作者：
F. C. Graham;P. Horn;Linyuan Lu
本文考虑一个宿主图G的随机子图Gp，它是由G的每条边以概率p保留而成的。我们解决了确定巨分支出现的临界值p（作为G的函数）的问题。假设G满足一些（温和的）条件取决于它的谱间隙和它的度序列的高阶矩。我们定义二阶平均度为= dv d2 v /（dv dv），其中dv表示v的度.我们证明了对任意p> 0，如果p >（1 + p）/，则渐近几乎必然地，被分解的子图Gp有巨分支.在另一个方向上，如果p >（1 − n）/，那么几乎肯定，被分解的子图Gp不包含巨分支。该论文的扩展摘要出现在WAW 2009会议记录中[Chung et al. 09]。主要定理是加强了更弱的假设。
Abstract We consider a random subgraph Gp of a host graph G formed by retaining each edge of G with probability p. We address the question of determining the critical value p (as a function of G) for which a giant component emerges. Suppose G satisfies some (mild) conditions depending on its spectral gap and higher moments of its degree sequence. We define the second-order average degree to be = Σ v d 2 v /(Σ v d v ), where d v denotes the degree of v. We prove that for any ∊ > 0, if p > (1 + ∊)/, then asymptotically almost surely, the percolated subgraph Gp has a giant component. In the other direction, if p > (1 − ∊)/, then almost surely, the percolated subgraph Gp contains no giant component. An extended abstract of this paper appeared in the WAW 2009 proceedings [Chung et al. 09]. The main theorems are strengthened with much weaker assumptions.