|
ABSTRACT:
Consider bond percolation on the hypercube {0,1}^n at the critical edge probability p_c defined such that the expected cluster size equals 2^{n/3}, where 2^{n/3} acts as the cube root of the number of vertices of the n-dimensional hypercube. Percolation on the hypercube was proposed by Erdos and Spencer (1979), and has proved to be substantially harder than percolation on the complete graph due to the non-trivial geometry of the hypercube.
In this talk, I will describe the phase transition for percolation on the hypercube, and show that it shares many features with that on the complete graph.
In previous work, we have identified the subcritical and critical regimes of percolation on the hypercube. In particular, we know that for p=p_c(1+O(2^{-n/3})), the largest connected component is of size roughly 2^{2n/3} and that this quantity is non-concentrated. So far, we were missing an analysis of the behavior of the largest connected component just above the critical value.
In this work, we identify the supercritical behavior of percolation on the hypercube by showing that, for any sequence \varepsilon_n tending to zero, but \varepsilon_n being much larger than 2^{-n/3}, percolation on the hypercube with edge probability p=p_c(1+\varepsilon_n) has, with high probability, a unique giant component of size (2+o(1))\varepsilon_n 2^n.
A main tool is the use of non-backtracking random walk, which we use to show that long percolation paths have endpoints that are almost uniform on the hypercube.
This is joint work with Asaf Nachmias, building on previous work with Markus Heydenreich, Gordon Slade, Christian Borgs, Jennifer Chayes and Joel Spencer.
|
|
