Percolation on finite graphs and isoperimetric inequalities

• 成果类型: Article
• 署名作者: Alon, N; Benjamini, I; Stacey, A
• 署名单位: Microsoft; Tel Aviv University; Tel Aviv University; University of Cambridge
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/009117904000000414
• 发表日期: 2004
• 页码: 1727-1745
• 关键词: product

摘要

Consider a uniform expanders family G(n) with a uniform bound on the degrees. It is shown that for any p and c > 0, a random subgraph of G(n) obtained by retaining each edge, randomly and independently, with probability p, will have at most one cluster of size at least c\G(n)\, 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.