4 - More on phase transitions

Summary

In this chapter we examine the subcritical and the supercritical phase of a random network in more detail, with particular reference to bond percolation on the square lattice. The results presented lead to the exact determination of the critical probability of bond percolation on the square lattice, which equals 1/2, and to the discovery of additional properties that are important building blocks for the study of information networks that are examined later in the book.

One peculiar feature of the supercritical phase is that in almost all models of interest there is only one giant cluster that spans the whole space. This almost immediately implies that any two points in space are connected with positive probability, uniformly bounded below. Furthermore, the infinite cluster quickly becomes extremely rich in disjoint paths, as p becomes strictly greater than p_c. So we can say, quite informally, that above criticality, there are many ways to percolate through the model. On the other hand, below criticality the cluster size distribution decays at least exponentially fast in all models of interest. This means that in this case, one can reach only up to a distance that is exponentially small.

To conclude the chapter we discuss an approximate form of phase transition that can be observed in networks of fixed size.

Preliminaries: Harris–FKG Inequality

We shall make frequent use of the Harris–FKG inequality, which is named after Harris (1960) and Fortuin, Kasteleyn and Ginibre (1971). This expresses positive correlations between increasing events.