Is the Erdős–Rényi giant component result applicable here?

Question

Consider a matrix whose elements are independently assigned a value $1$ with probability $p$ and a value $0$ with probability $1-p$.

Define a cluster of cells as a maximal connected component in the graph of cells with the value of $1$, where edges connect cells whose rows and columns both differ by at most $1$ (so up to eight neighbours for each cell).

I numerically plotted the number of clusters vs. the probability $p$, for matrices of size $8\times 8, 16 \times 16, 32 \times 32, 64 \times 64, 128 \times 128, 256 \times 256.$ The results came out like:

Plot: Number of clusters per unit area vs. probability p for different L's:

(Note that "black cluster" refers to the cluster of elements labelled with $1$)

Is it possible to reformulate this matrix model to match the Erdős–Rényi graph model? I was wondering whether the Giant component result will be applicable for this model and whether it will be possible to reframe this problem to match the Erdős–Rényi model. I think they're related but not sure exactly how. One problem is that the $p$ here is the probability of a node being 1, rather than the probability of the existence of an edge, unlike the Erdős–Rényi model.

This question is a result of Mike's comment, here:

So I am really not sure of the exact probability that there would be a giant component and so I cannot guarantee a giant component likely for the specific value of $p=1/2$ (sorry). But my thinking was along the lines of the analysis of the size of the components of Erdos-Renyi graphs....checking that out may be useful.

Answer 1

As Simon L Rydin Myerson says, this is a percolation problem, in particular a site (vertex) percolation problem on a particular graph. Like him, I don't know offhand results for this square-lattice-with-diagonals.

In these situations you typically expect behaviour that, at least on a very coarse level, mirrors that observed in Erdős–Rényi random graphs. However, even for the more closely related bond (edge) percolation (where adjacent vertices are connected independently with probability $p$) the specifics of the results and the techniques used to prove them differ enough that neither result is a simple application of the other.

The essential difference is that vertices in lattices start out much further apart than vertices in a complete graph $K_n$. It's easier for vertices to be isolated (as the maximum number of vertices they could possibly be adjacent to is lower) and also easier to separate off large clumps of vertices from the rest of the graph: you only need to find an empty ring of vertices surrounding a cluster, rather than an enormous bipartite subgraph which happens to contain no edges. The end result is that percolation in lattices is typically studied at much higher values of $p$ than the Erdős–Rényi process—constant $p$ rather than $p \approx 1/n$—and different probabilistic tools are of use for studying the random variables that arise.

Answer 2

It sounds like you have a percolation problem. In percolation theory one has a lattice, typically in the plane or in 3-space, and each vertex is "porous" independently with probability $p$. The question is to describe the connected components of the set of porous vertices. It is common to restrict to a finite box, as in your example. One expects a similar behaviour to the Erdős–Rényi graph model, and there are many cases in which it is proved (although there may be less emphasis on the size of the small components). Edit: As Ben Barber points out in his answer, the techniques used are quite different to the Erdős–Rényi case, and one needs a much larger value of $p$ in order to expect a giant component.

For some impressive-sounding real-world motivation one might imagine oil percolating through rock; it can only pass through porous areas, and the question is whether it eventually occupies a positive proportion of the rock (in which case one can drill into it and make some money). For many researchers the actual motivation is probably more to do with theoretical understanding of phase transitions.

These problems are well studied, for example there are some introductory lecture notes here. On a casual inspection I cannot actually find an example where diagonal connections (cells connected only at their corners) are permitted, as in your question. Frustratingly I actually remember playing with a simulation of exactly your example in a physics lesson back in my schooldays. Maybe I can track it down.