Edge percolation on a random regular graph of low degree

• 成果类型: Article
• 署名作者: Pittel, Boris
• 署名单位: University System of Ohio; Ohio State University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/07-AOP361
• 发表日期: 2008
• 页码: 1359-1389
• 关键词: giant component; finite graphs; triangle condition; random subgraphs; degree sequence; emergence; point

摘要

Consider a uniformly random regular graph of a fixed degree d >= 3, with it vertices. Suppose that each edge is open (closed), with probability p(q = 1 - p), respectively. In 2004 Alon, Benjamini and Stacey proved that p* = (d - 1)(-1) is the threshold probability for emergence of a giant component in the subgraph formed by the open edges. In this paper we show that the transition window around p* has width roughly of order n(-1/3). More precisely, suppose that p = p(n) is such that omega := n(1/3)vertical bar p-p*vertical bar --> infinity. If p < p*, then with high probability (whp) the largest component has O((p - p*)(-2) log n) vertices. If p > p*, and log omega >> log log n, then whp the largest component has about n (1 - (p pi + q)(d)) asymptotic to n (p - p*) vertices, and the second largest component is of size (p - p*)(-2)(log n)(1+o(1)), at most, where pi = (p pi + q)(d-1), pi is an element of (0, 1). If omega is merely polylogarithmic in n, then whp the largest component contains n(2/3+o(1)) vertices.