Mixing time and diameter of the percolated hypercube

We study bond percolation on the d-dimensional hypercube Q^d with edge retention probability p=c/d. It is well known that when c>1 is fixed, a unique giant component emerges. In this regime, we resolve long-standing conjectures of Bollobás, Kohayakawa, and Łuczak (1994) and of Benjamini and Mossel (2003), showing that the typical diameter of the giant component is Θ(d), and that the mixing time of the lazy random walk on it is Θ(d^2). In the talk, we will introduce the notion of mixing time and its connection to expansion properties of subsets of the giant. We will then discuss some of the key obstacles in obtaining this result, and in particular why classical sprinkling techniques are insufficient for this problem. Finally, we will explain how our new approach - based on analysing the effect of small perturbations and establishing stability under thinning - overcomes these obstacles. This method also yields tight large-deviation estimates for the size of the giant.  

Based on joint work with Michael Anastos, Lyuben Lichev, and Maksim Zhukovskii.