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

2004/01/08 by Christian Borgs, Borgs, Christian, Jennifer T. Chayes +7 · 1 citation
Mathematics · #05C80 #60K35 #82B43 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05C80 #msc:60K35 #msc:82B43

paper · pdf · doi:10.48550/arxiv.math/0401071

14 pages

arxiv created 2004/01/08 · arxiv updated 2009/12/01

Abstract

We study random subgraphs of the n-cube \0,1\ⁿ, where nearest-neighbor edges are occupied with probability p. Let p_c(n) be the value of p for which the expected cluster size of a fixed vertex attains the value λ2^n/3, where λ is a small positive constant. Let ε=n(p-p_c(n)). In two previous papers, we showed that the largest cluster inside a scaling window given by |ε|=Θ(2^-n/3) is of size Θ(2^2n/3), below this scaling window it is at most 2(log2) nε^-2, and above this scaling window it is at most O(ε2ⁿ). In this paper, we prove that for p - p_c(n) ≥ e^-cn^1/3 the size of the largest cluster is at least Θ(ε2ⁿ), which is of the same order as the upper bound. This provides an understanding of the phase transition that goes far beyond that obtained by previous authors. 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.

Cited by

• Diameter and mixing time of the giant component in the percolated hypercube

Related

• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Expansion in supercritical random subgraphs of the hypercube and its\n consequences
• The phase transition in Chung-Lu graphs
• The phase transition in random graphs - a simple proof