Matthew Tointon

Phase transition for percolation on finite vertex-transitive graphs

Abstract: Let G be an infinite connected graph. Suppose now that you delete certain edges of G at random - say each edge is deleted independently with probability 1-p, or retained with probability p. What is the probability that the configuration you end up with contains an infinite connected component? This is the kind of question that is traditionally the subject of percolation theory.

If G is a *finite* graph then it still makes sense to retain edges independently at random with probability p, but it is no longer very interesting to ask whether the resulting configuration contains an infinite connected component. Instead, one can ask something like "what is the probability that at least half of the vertices of G lie in a single connected component?” In ongoing work, Tom Hutchcroft and I show that if G is vertex transitive of bounded degree and satisfies a certain (essentially necessary) diameter condition then there is some p < 1, independent of G, for which this probability is at least 0.999999999. This confirms a well-known conjecture of Alon, Benjamini and Stacey.

N/A