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 language | English (US) |
---|---|
Pages (from-to) | 395-410 |
Number of pages | 16 |
Journal | Combinatorica |
Volume | 26 |
Issue number | 4 |
DOIs | |
State | Published - Aug 2006 |
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics