TY - JOUR

T1 - Random subgraphs of finite graphs, III. The phase transition for the n-cube

AU - Borgs, C.

AU - Chayes, J.T.

AU - Hofstad, van der, R.W.

AU - Slade, G.

AU - Spencer, J.

PY - 2006

Y1 - 2006

N2 - We study random subgraphs of the n-cube {0,1}n, where nearest-neighbor edges are occupied with probability p. Let pc(n) be the value of p for which the expected size of the component containing a fixed vertex attains the value ¿2n/3, where ¿ is a small positive constant. Let e=n(p-pc(n)). In two previous papers, we showed that the largest component inside a scaling window given by |e|=T(2-n/3) is of size T(22n/3), below this scaling window it is at most 2(log 2)ne-2, and above this scaling window it is at most O(e2n). In this paper, we prove that for the size of the largest component is at least T(e2n), which is of the same order as the upper bound. The proof is based on a method that has come to be known as "sprinkling," and relies heavily on the specific geometry of the n-cube.

AB - We study random subgraphs of the n-cube {0,1}n, where nearest-neighbor edges are occupied with probability p. Let pc(n) be the value of p for which the expected size of the component containing a fixed vertex attains the value ¿2n/3, where ¿ is a small positive constant. Let e=n(p-pc(n)). In two previous papers, we showed that the largest component inside a scaling window given by |e|=T(2-n/3) is of size T(22n/3), below this scaling window it is at most 2(log 2)ne-2, and above this scaling window it is at most O(e2n). In this paper, we prove that for the size of the largest component is at least T(e2n), which is of the same order as the upper bound. The proof is based on a method that has come to be known as "sprinkling," and relies heavily on the specific geometry of the n-cube.

U2 - 10.1007/s00493-006-0022-1

DO - 10.1007/s00493-006-0022-1

M3 - Article

VL - 26

SP - 395

EP - 410

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 4

ER -