Percolation on finite graphs and isoperimetric inequalities
Percolation on finite graphs and isoperimetric inequalities
复制标题
DOI：
10.1214/009117904000000414
复制
发表时间：
2002-07
影响因子：
2.3
通讯作者：
N. Alon;I. Benjamini;A. Stacey
中科院分区：
文献类型：
--
作者：
N. Alon;I. Benjamini;A. Stacey
考虑一个一致扩张族Gn，其度有一个一致界。证明了对任意p和c>0，通过以概率p随机独立地保留每个边而得到的Gn的随机子图至多有一个大小至少为c的簇|GN|本文应用Ajtai，Komlos和Szemeredi [Combinatorica 2（1982）1-7]的方法，得到了关于有限高围长正则扩张图的随机子图出现巨连通区的临界概率的一些新结果，以及Kesten关于高维键渗流临界概率的一个结果的简单证明。本文提出了有限传递图上渗透的几个问题和几个定理。
Consider a uniform expanders family Gn with a uniform bound on the degrees. It is shown that for any p and c>0, a random subgraph of Gn obtained by retaining each edge, randomly and independently, with probability p, will have at most one cluster of size at least c|Gn|, with probability going to one, uniformly in p. The method from Ajtai, Komlos and Szemeredi [Combinatorica 2 (1982) 1–7] is applied to obtain some new results about the critical probability for the emergence of a giant component in random subgraphs of finite regular expanding graphs of high girth, as well as a simple proof of a result of Kesten about the critical probability for bond percolation in high dimensions. Several problems and conjectures regarding percolation on finite transitive graphs are presented.