The percolation phase transition in the Hamming cube

460 views · Published 17 August 2016 · 1:01:15 · Indexed 31 October 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

Consider percolation on the Hamming cube {0,1}^n at the critical probability p_c (at which the expected cluster size is 2^{n/3}). It is known that if p=p_c(1+O(2^{-n/3}), then the largest component is of size roughly 2^{2n/3} with high probability and that this quantity is non-concentrated. We show that for any sequence eps(n) such that eps(n)2^{-n/3} and  eps(n)=o(1) percolation at p_c(1+eps(n)) yields a largest cluster of size (2+o(1))eps(n)2^n.    This result settles a conjecture of Borgs, Chayes, van der Hofstad, Slade and Spencer.    Joint work with Remco van der Hofstad.

More from this channel