Abstract
It is well known that the behaviour of a random subgraph of a ddimensional hypercube, where we include each edge independently with probability p, undergoes a phase transition when p is around 1 d. More precisely, standard arguments show that just below this value of p all components of this graph have order O(d) with probability tending to one as d→∞ (whp for short), whereas Ajtai, Komlós and Szemerédi (Combinatorica 2 (1982) 1–7) showed that just above this value, in the supercritical regime, whp there is a unique “giant” component of order (Formula Presented). We show that whp the vertex expansion of the giant component is inverse polynomial in d. As a consequence, we obtain polynomial in d bounds on the diameter of the giant component and the mixing time of the lazy random walk on the giant component, answering questions of Bollobás, Kohayakawa and Łuczak (Random Structures and Algorithms 5 (1994) 627–648) and of Pete (Electron. Commun. Probab. 13 (2008) 377–392). Furthermore, our results imply lower bounds on the circumference and Hadwiger number of a random subgraph of the hypercube in this regime of p, which are tight up to polynomial factors in d.
Original language | English |
---|---|
Pages (from-to) | 127-156 |
Number of pages | 30 |
Journal | The Annals of Probability |
Volume | 51 |
Issue number | 1 |
DOIs | |
Publication status | Published - 2023 |
Keywords
- math.CO
- math.PR
- Hypercube percolation
- Graph expansion
ASJC Scopus subject areas
- Statistics and Probability
- Statistics, Probability and Uncertainty
Fields of Expertise
- Information, Communication & Computing