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.
|
 |
Random Subgraphs Of Finite Graphs: III. The Phase Transition For The n-Cube
| |
|
Original Paper
Random Subgraphs Of Finite Graphs: III. The Phase Transition For The n-Cube
Christian Borgs1 , Jennifer T. Chayes2 , Remco van der Hofstad3 , Gordon Slade4 and Joel Spencer5 
| (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 λ2 n/3, where λ is a small positive constant. Let ε= n( p− pc( n)). In two previous papers, we showed that the largest component inside a scaling window given by |ε|=Θ(2 −n/3) is of size Θ(2 2n/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

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.
Mathematics Subject Classification (2000): 05C80 - 82B43
Fulltext Preview (Small, Large)
|
|
|
|
|
|