ABSTRACT

Random subgraphs of the n-cube

Remco van der Hofstad, April 9, 2003

We study random subgraphs of the hypercube {0,1}^n where bonds are occupied with probability p. We define the critical value p_c(n) to be the value of p for which the expected cluster size of any fixed point attains the value 2^{n/3}. We believe that the critical threshold has an asymptotic expansion in powers of $1/n$, and are working on a proof of this statement. In particular, we show that $p_c(n)$ is approximately equal to n^{-1}+n^{-2}+7/2n^{-3}, which is a vast improvement compared to previous work. The main results show that p_c(n) really is the critical threshold. Indeed, both the expected cluster size and the largest cluster jump from polynomially large in n for p< p_c(n)-\delta n^{-t} to exponentially large for p> p_c(n)-\delta n^{-t} and every t>0. We obtain detailed estimates on the asymptotics of both the largest and the expected cluster sizes on both sides of the critical threshold. The proofs mainly use methods from both mathematical physics, such as differential inequalities and the lace expansion. We also use certain methods from combinatorics, such as variance estimates and sprinkling arguments. This is joint work with Christian Borgs, Jennifer Chayes, Gordon Slade and Joel Spencer.

Back to the history of the seminar or the Colloquium Stochastiek homepage.

Igor Grubisic (grubisic@math.uu.nl)