Percolation in the Erdős–Rényi model, and beyond
This set of notes is created to procrastinate the production scientific results and to relive the excitement I felt during PHYS 7653, advanced statistical mechanics, taught by Prof. Veit Elser in Fall 2019.
Model
The model is introduced by two mathematical giants, Paul Erdős and Alfréd Rényi in 1960. It has the following inputs:
a set of points as vertices.
a probability which describes the probability of having an edge between any pair of vertices.
Note that the model lives in dimensions: there is no embedding into a manifold. We are interested in the limit where and fixed. The probability is defined such that . Macroscopically, this model describes a set of graphs.
Calculations on small clusters
A simple calculation we can do is the distribution of degree for a given vertex:
Taking the limit of and using Stirling's approximation, we find that the probability reduces to a Poisson distribution:
We want to calculate some more interesting quantities, say the number of triangles in the system. To do this, let's define to be the set of all triples in the system: . Define the indicator to be if is a triangle and if not. Since all triplets in the system are equivalent,
Given , if it is indeed a triangle, then its three edges have to be connected; also, its three vertices cannot be connected to any other vertex. Hence, which yields
One can similarly calculate the expected number for any other graph with vertices and edges. One will find that
Through this calculation, we find that forming cycles are costly: the only subgraphs whose quantities scale linearly with are trees.
All the graphs we studied before are finite, small clusters compared to the system size : there might be the case where there exists a cluster whose size scales linearly with . When this happens, we say that the system percolates. The central question to ask in this note is: when will the system percolate?
At this moment, the readers informed in physics should feel the plug in their stomach: this vaguely has the flavor of asking when a bosonic system will condense. This will be made more precise in a later section. The physical approach we often take on BECs is that, we calculate the thermal distribution of bosonic particles and see if the thermal distribution can take all the particles; if it can't take all the particles, the amount that overflows (which is a macroscopic quantity) condenses into the ground state. We will ask a similar question here: What fraction of vertices are in finite clusters as ?
Percolation transition
As we have shown above, as , the most important contributions to these clusters come from trees. Let's calculate the number of trees of size , . Similar to before, we take the set of all -tuples and calculate the expectation that they form trees. For a particular tree configuration in a particular tuple, the probability is ; for a particular cluster , there are different labeled trees. In the end, the expected number of trees with size is
Let be the fraction of vertices in finite clusters, similar to the fraction of particles not in the condensate.
where is the Lambert function. Although there are many conventions, here we take the convention where . Hence and there is no percolation. The reader is now advised to leave the website, for they seem to have wasted some of their precious time and should avoid further sunken cost.
What is wrong with the calculation before? One - physically we know that the calculation can't be right. In the limit , almost all vertices should be in the same cluster. Two - mathematically the treatment is not rigorous: the Lambert function isn't really well defined as we have written it!
Lambert W function
Note that the Lambert function is defined as the inverse of the function : that is, .
However, the inverse is not well defined: the equation has two solutions, and . Which branch are we picking? Does equal to or ? We define to be the other solution of .
To make sure that , we will pick the branch related to ; that is, the branch with smaller values. Now is only defined on whose values run from to . Hence, the function has the following definition:
This means that our calculation of – number of vertices in small clusters – is actually not correct. It will be
We see a clear transition: the system percolates when . There is an extensive amount of particles that do not live in small clusters; they must live in a huge cluster that has size of order .
Duality
Since , it is natural to suspect that the system will behave similarly although we have different values for . To see that, we consider the following quantity: let be the size of tree a vertex belongs to, averaged over vertices in finite clusters. Define . By construction,
Given that , . Hence
We hence see the duality: at either or , the system exhibits the same behavior, except for the percolating cluster.
BEC as a graph model
I would like to sketch how BEC becomes a graph model. Consider the partition function of bosons:
Forgetting all the macroscopic details, we can try to study the structure of the permutation . Which kinds of permutations dominate the sum? It is not unimaginable that when BEC condensation happens, the sum is dominated by permutations containing a cycle of length order - this is called cycle percolation, and it has been studied intensively[1][2].
References
[1] | A. Suto, Percolation transition in the Bose gas (1993). DOI |
[2] | A. Suto, Percolation transition in the Bose gas II (2002). arXiv |