## 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 Θ(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 p - p_{c}(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