1
$\begingroup$

Context:

This a sequel to the question: Is the Erdős–Rényi 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 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:

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

$\endgroup$
  • $\begingroup$ As mentioned in those answers, it seems your model is one in percolation theory. I recommend having a look at basic references in that subject, e.g. the book "Percolation" by Grimmett. $\endgroup$ – j.c. Apr 29 '18 at 15:45
  • $\begingroup$ @j.c. I have looked through a few percolation theory books and papers. Couldn't find anything related to this particular model. $\endgroup$ – user123818 Apr 29 '18 at 15:59
  • $\begingroup$ @JamesMartin I'm a bit confused by your comment. Firstly you say that "It absolutely is a percolation model (specifically, a site percolation model)" and then you say that "percolation theory absolutely does concern itself with questions such as the size of the largest cluster within a finite box". Sure, I know there are similar percolation models for an infinite square grid. But I'm concerned with the variation of the size of clusters w.r.t $p$, which percolation theory does not go into. You're right my question as of now is still vague, but I will post a more rigorous version soon. $\endgroup$ – user123818 Apr 30 '18 at 19:47
  • $\begingroup$ @JamesMartin To be more general let's say that I'm interested in knowing how the probability of occurrence of different possible cluster sizes varies as $p$, increases from $0$ to $1$. For example, can mathematically calculate what would be the probability of occurrence of a size $100$ cluster in a $1000\times1000$ square grid at $p=0.40$ ? $\endgroup$ – user123818 Apr 30 '18 at 20:05
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – James Martin Apr 30 '18 at 20:34
4
$\begingroup$

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" in the study of cellular automata.

The paper "Square lattice site percolation at increasing ranges of neighbor interactions" by K. Malarz, S. Galam 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", 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 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".

$\endgroup$
  • $\begingroup$ Thanks. Do you know any result related to why there is a tendency of giant cluster formation and what the rate of it is, beyond a certain probability $p$ in this type of model? $\endgroup$ – user123818 Apr 30 '18 at 5:37
  • $\begingroup$ I've added that part to my original question. Please check. I couldn't find any relevant result regarding giant cluster formation for Moore neighbourhoods. $\endgroup$ – user123818 Apr 30 '18 at 6:01
  • 1
    $\begingroup$ Thanks for the update. I'm reading Grimmet's book. But one thing I'm a bit confused about is how exactly they are defining an "open cluster". Could you explain that definition of "open cluster"? $\endgroup$ – user123818 Apr 30 '18 at 13:19
  • 1
    $\begingroup$ So you are essentially asking about the distribution of cluster sizes as a function of $p$. This is certainly of great interest in percolation theory but I don't believe the field has advanced to a point where it can provide you with all of the answers you seek. Instead, I think only a few of the lowest moments of this distribution have been studied: e.g. the expected size of the cluster at the origin is equal to the mean of the distribution you seek. $\endgroup$ – j.c. Apr 30 '18 at 20:42
  • 1
    $\begingroup$ Furthermore, exact answers for specific finite systems are unlikely to be known or of much interest -- you will have more luck seeking out asymptotic approximations, in which case you should try to take results derived for infinite-size systems and apply finite-size scaling. All of what I've said above is focused on what is known rigorously. You might find various simulations and heuristics if you search for physics papers with terms like "cluster size distribution percolation". $\endgroup$ – j.c. Apr 30 '18 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy