Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Original Paper

Random Subgraphs Of Finite Graphs: III. The Phase Transition For The n-Cube

Christian BorgsContact Information, Jennifer T. ChayesContact Information, Remco van der HofstadContact Information, Gordon SladeContact Information and Joel SpencerContact Information

(1)  Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA
(2)  Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA
(3)  Department of Mathematics and Computer Science, Eindhoven University of Technology, 513, 5600 MB Eindhoven, The Netherlands
(4)  Department of Mathematics, University of British Columbia, Vancouver, BC V6T 1Z2, Canada
(5)  Courant Institute of Mathematical Sciences, New York University, 251 Mercer St., New York, NY 10012, USA

Received: 6 May 2003  

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 ε=n(ppc(n)). In two previous papers, we showed that the largest component inside a scaling window given by |ε|=Θ(2n/3) is of size Θ(22n/3), below this scaling window it is at most 2(log 2)−2, and above this scaling window it is at most O(ε2n). In this paper, we prove that for $$
p - p_{c} {\left( n \right)} \geqslant e^{{cn^{{1/3}} }} 
$$ the size of the largest component is at least Θ(ε2n), 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.

Mathematics Subject Classification (2000):  05C80 - 82B43


Contact Information Christian Borgs (Corresponding author)
Email: borgs@microsoft.com

Contact Information Jennifer T. Chayes
Email: jchayes@microsoft.com

Contact Information Remco van der Hofstad
Email: rhofstad@win.tue.nl

Contact Information Gordon Slade
Email: slade@math.ubc.ca

Contact Information Joel Spencer
Email: spencer@cims.nyu.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this article
Export this article as RIS | Text
 
Referenced by
6 newer articles

  1. Nachmias, Asaf (2009) Mean-Field Conditions for Percolation on Finite Graphs. Geometric and Functional Analysis
    [CrossRef]
  2. van der Hofstad, Remco (2009) The second largest component in the supercritical 2D Hamming graph. Random Structures and Algorithms
    [CrossRef]
  3. Bollobás, Béla (2009) Clique percolation. Random Structures and Algorithms
    [CrossRef]
  4. BALOGH, JÓZSEF (2008) Majority Bootstrap Percolation on the Hypercube. Combinatorics Probability and Computing
    [CrossRef]
  5. Janson, Svante (2008) A new approach to the giant component problem. Random Structures and Algorithms
    [CrossRef]
  6. Angel, Omer (2007) Routing complexity of faulty networks. Random Structures and Algorithms
    [CrossRef]
Remote Address: 38.107.191.110 • Server: mpweb01
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)