Connectivity

Introduction In some cases, percolation is not sufficient, since it merely guarantees that an infinite number of nodes is connected somewhere in a graph or network. In fact the fraction of connected nodes may be quite small; it could easily be that most nodes are disconnected from the infinite component. Connectivity is a much more stringent condition; it requires that all nodes are connected a.s. Since the connectivity parameters, such as the radius of the disk graph, often need to be infinite for infinite graphs, we focus on finite graphs first, say on a square of area n , and then study the connectivity behavior of the graph as n ↦ ∞ . We start our discussion with the connectivity of the random lattice. Connectivity of the random lattice We consider a box B ( n ) of size n × n vertices of the square lattice 2 . As in the bond percolation model, each edge is open with probability p . We would like to find the condition on p under which all vertices in B ( n ) are connected, asymptotically as n ↦ ∞. We established that the critical probability for bond percolation on 2 is p c = 1/2. Recall that θ( p ) denotes the probability that the origin o belongs to the infinite component. If p > 1/2, there exists a unique infinite component on the lattice, and each vertex in B ( n ) is connected to it with probability θ( p ).