Context:
--------


This a sequel to the question: [Is the Erdős–Rényi giant component result applicable here?](https://mathoverflow.net/questions/298758/is-the-erd%C5%91s-r%C3%A9nyi-giant-component-result-applicable-here)



> 
> 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).
> 
> 
> Is it possible to reformulate this matrix model to match the
>  Erdős–Rényi graph model? I was wondering whether the [Giant
>  component](https://en.wikipedia.org/wiki/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.
> 
> 
> 


According to [@Ben Barber's answer](https://mathoverflow.net/a/298789/123818):



> 
> 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 different 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.
> 
> 
> 


Further, [@Simon L Rydin Myerson](https://mathoverflow.net/questions/298758/is-the-erd%C5%91s-r%C3%A9nyi-giant-component-result-applicable-here) says:



> 
> 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.
> 
> 
> 


Question:
---------


It seems that random matrix model, in this case, cannot exactly be modelled as an Erdos-Reyni graph. 


**So, basically, my question is, can this particular random matrix model be related to any existing graph theory model leaving aside the Erdos-Reyni model (where diagonal connections are permitted)?**


**I'd actually be interested to know if there are some existing results about *why* giant clusters are formed in such square grids beyond a certain value of $p$ (I'm trying to make an analogy with the [giant component formation](https://en.wikipedia.org/wiki/Giant_component) in Erdos Reyni graphs).**


P.S: Please note that this is **NOT A PERCOLATION THEORY PROBLEM**. Percolation theory is concerned with the formation of spanning clusters, which is not what I meant by "giant component". A "giant component" need not necessarily be a spanning cluster. If all the cells leaving aside the edge cells get filled even that is a giant component without being a spanning cluster.



Can this particular random matrix model be converted/related to any existing graph theory model?
To answer your specific question, I would call your model "site percolation on the square lattice with nearest-neighbor (NN) and next-nearest-neighbor (NNN) bonds". Apparently this connectivity relationship is also called the ["Moore neighborhood"](https://en.wikipedia.org/wiki/Moore_neighborhood) in the study of cellular automata.


The paper ["Square lattice site percolation at increasing ranges of neighbor interactions" by K. Malarz, S. Galam](https://arxiv.org/abs/cond-mat/0408338) estimates the percolation threshold in this and other similar graphs related to the square lattice.


Now, a few broader points about percolation theory. As you state in a comment, in the percolation theory literature there doesn't seem to be anything treating your particular question (the total number of clusters per site on this specific graph). However, I would not then brush all these references aside. The way to look at these results is not individually but as part of a bigger picture. Indeed, for any mathematical result, you should look at the proofs to see whether the techniques used can be generalized to other cases; e.g. can something stated for the triangular or square lattice be adapted to your graph?


In percolation (and many other models coming from statistical physics), there actually is a more profound big picture, the "[universality principle](https://en.wikipedia.org/wiki/Percolation_theory#Universality)", where certain features (typically exponents which appear in scaling functions) are believed to depend only on the dimensionality of the graph and not its local details. This is a topic of active research, so much of what is out there is only conjectural; however it has proven to be of enormous value in seeking out new results and connections. Chapter 9 of Grimmett's book "Percolation" might be one place to start reading, though it may only make sense if you know the definitions from earlier chapters.


In that spirit, I can recommend [this paper of Mertens, Jensen and Ziff](https://arxiv.org/abs/1602.00644) which discusses the features of the "number of clusters per unit area" from this point of view. Perhaps you could try to see what their results suggest about your graph and then see if you can adapt their methods to your case.


**update in response to edit**:


You still seem to object to my suggestion to dig deeper into percolation theory. I will address your concerns once more here.


It is indeed true that one of the classical definitions of the percolation phase transition is based on the appearance of *spanning* clusters. However, if you have a look at Grimmett's book, or most other rigorous mathematical sources, you will see that the modern definition of the critical probability there is in terms of the existence of an infinite open cluster. (Finite, large systems are related to this limit by the theory of "finite-size scaling").


[The probability of the existence of a cluster spanning two given sides of a large box, or more generally, two arbitrary boundary segments, is also known as the "crossing probability" and there are beautiful results about it in 2D by Cardy and Smirnov which is explained in Chapter 7 of the book "Percolation" by Bollobás and Riordan.]


In any case spanning clusters and giant clusters are highly correlated and one can show that they lead to the same definition of the critical probability. In a few more words, it is not hard to bound the probability of events like the one you describe in your edit and show that it goes to zero very quickly as the size of the system grows.


Note also that the paper of Mertens, Jensen and Ziff that I mention above does not rely at all on the crossing or lack of crossing of the clusters that they count. I've also just noticed that Chapter 4 of Grimmett's book is devoted to this function as well, which they call $\kappa$, "the number of open clusters per vertex".


