Random Subgraphs of Finite Graphs: I. The Scaling Window Under the Triangle Condition

We study random subgraphs of an arbitrary finite connected transitive graph G obtained by independently deleting edges with probability 1¡p. Let V be the number of vertices in G, and let ­ be their degree. We define the critical threshold pc = pc(G; ¸) to be the value of p for which the expected cluster size of a fixed vertex attains the value ¸V 1=3, where ¸ is fixed and positive. We show that for any such model, there is a phase transition at pc analogous to the phase transition for the random graph, provided that a quantity called the triangle diagram is sufficiently small at the threshold pc. In particular, we show that the largest cluster inside a scaling window of size jp¡pcj = £(­¡1V ¡1=3) is of size £(V 2=3), while below this scaling window, it is much smaller, of order O(²¡2 log(V ²3)), with ² = ­(pc¡p). We also obtain an upper bound O(­(p ¡ pc)V ) for the expected size of the largest cluster above the window. In addition, we define and analyze the percolation probability above the window and show that it is of order £(­(p¡pc)). Among the models for which the triangle diagram is small enough to allow us to draw these conclusions are the random graph, the n-cube and certain Hamming cubes, as well as the spread-out n-dimensional torus for n > 6.