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

Christian Borgs, Jennifer T. Chayes, Remco Van Der Hofstad, Gordon Slade, Joel Spencer

Research output: Contribution to journalArticlepeer-review

Abstract

We study random subgraphs of the n-cube {01} n where nearest-neighbor edges are occupied with probability p. Let p c (n) be the value of p for which the expected size of the component containing 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 component inside a scaling window given by |ε|=Θ(2-n/3) is of size Θ(22n/3) below this scaling window it is at most 2(log 2)nε -2 and above this scaling window it is at most O(ε2 n ). In this paper we prove that for p - pc(n)≥ e-cn1/3 the size of the largest component is at least Θ(ε2 n ) 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.

Original languageEnglish (US)
Pages (from-to)395-410
Number of pages16
JournalCombinatorica
Volume26
Issue number4
DOIs
StatePublished - Aug 2006

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Random subgraphs of finite graphs: III. The phase transition for the n-cube'. Together they form a unique fingerprint.

Cite this