Remco W. van der Hofstad
| We study random subgraphs of finite graphs where bonds are occupied with probability p. Examples are the complete graph on {1,..., n}, the hypercube {0,1}n or tori {0,...r-1}n for some n>6. This problem has attracted considerable attention in the combinatorics community, and detailed results are proven for the random graph, which is the random subgraph of the complete graph. The main results are the description of the largest connected component, and how this largest connected component has a phase transition when p varies from below 1/n to above 1/n. At the same time, in statistical mechanics, the problem of percolation, which is equivalent to random subgraphs of infinite graphs, has inspired substantial and deep work. Even though these two fields are closely related, theory and methodology have evolved almost independently, and the two communities even use different language. In this talk we will describe relations between the two fields, and show how one can use ideas and methodology from both fields to our benefit. More precisely, in analogy with the random graph, we define the critical value pc to be the value of p for which the expected cluster size of any fixed point attains the value V1/3, where V is the volume of the graph. The main results show that pc really is the critical threshold when we assume a certain simple random walk triangle condition on the finite graph. Such a triangle condition has appeared in the past in work of Aizenman and Newman, and Aizenman and Barsky, and implies what is called mean-field behaviour. This is joint work with Christian Borgs, Jennifer Chayes, Gordon Slade, and Joel Spencer. |