Site Percolation on Multi-dimensional Lattice
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematical Physics. The day in mathematical physics: rigorous models of physical systems.
Kai: We're looking at the paper: "Site Percolation on Multi-dimensional Lattice".
Mira: Here's the gist of the paper. Critical Probability of Site Percolation on Zd is 1/d Vertices (sites), open with the smallest probability pH, percolate when they form an infinite open path from graph’s origin v0 Usually, pH values are approximated, but there are a few instances of special lattices with the exact results In finite graph Zd k, d pairs of opposite arcs are k edges away from v0 If there is an open path from v0 to v∈Ak(Zd): k → ∞, Zd percolates The Definition of Percolation on Zd The paper defines site percolation on the lattice Zd as the condition where vertices, open with the smallest probability pH, percolate when they form an infinite open path from graph’s origin v0.
Kai: The structure of the graph is described using basis B(Zd) and integers ai(v) to assign a place to vertex v ∈ Zd k.
Mira: The path length →v = kvk = X d i=1 ai(v) ≤ k ∀v∈Zd k.
Kai: Neighbors of v can be partitioned into d up-step neighbors traversed via ↑i and d down-step neighbors traversed via ↓i.
Paper summary: Kai: So to recap, this paper "Site Percolation on Multi-dimensional Lattice" is focused on defining site percolation specifically for these multi-dimensional lattices Zd >
Mira: The thesis is that they establish the critical probability pH Zd is exactly one over d, where d represents the dimension of the lattice >
Kai: They start by defining percolation as an infinite open path starting from the origin vertex zero if those sites are open with a probability smaller than or equal to this value >
Mira: The paper claims that they derive this exact result by using two specific inequalities based on analyzing how paths extend and then taking the limit as k goes to infinity >
Kai: It matters because it gives us a concrete number for a fundamental property of connectivity on these types of graphs, which is usually hard to nail down analytically >
Lev: So, it’s like they’re giving us the exact tipping point for whether things connect infinitely or not based on the lattice dimension >
Mira: Right. It grounds the general idea of percolation in a very specific mathematical context using these path counting arguments to show that one over d is indeed that sharp limit >
Conclusion: Kai: So looking at this paper "Site Percolation on Multi-dimensional Lattice" by Marko Puljic, it really boils down to this exact critical probability one over d >
Mira: It’s a result that is quite elegant because they managed to prove it exactly for the lattice Zd, which means you don't have to guess or approximate that value when you work with these specific dimensions >
Lev: For someone who builds real hardware, this means we know precisely where we need to tune our physical parameters if we want that infinite path behavior to emerge >
Kai: It gives us a target. If we are trying to build something that exhibits this connectivity, the mathematical theory tells us exactly what the smallest probability pH needs to be >
Mira: And it points toward the challenge of engineering that threshold. We know it exists, but realizing that exact probability on physical hardware with low noise is the next big hurdle >
Marko Puljic
math-ph, cs.DM, math.CO, math.MP
Submitted: 2013-07-10
Updated: 2026-10-30
Comments: There is an error in definition of percolation in the first sentence: "Vertices (sites), open with the smallest probability pH, percolate when they form an infinite open path from graph's origin v0." Vertices percolate when the probability of the open path from an origin to the infinity is positive
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 51/100
The gist: Critical Probability of Site Percolation on Zd is 1/d Vertices (sites), open with the smallest probability pH, percolate when they form an infinite open path from graph’s origin v0 Usually…
Key concepts
- Site Percolation on Zd
- This is a model where vertices on a lattice Zd are randomly opened or closed. The goal is to find the minimum probability pH such that if enough vertices are open with this probability, there will be an infinite connected path starting from a specific origin vertex v0.
- k-paths and ψk
- The analysis uses k-paths, which are paths built primarily through up-step traversals. The expected number of these paths is denoted as ψk = (dp)k. This counting method helps determine the likelihood of finding an infinite open path in the lattice Zd.
- Critical Probability pH Zd
- This is the specific probability pH that determines whether site percolation occurs on a lattice Zd. The paper rigorously proves that for this particular lattice, this critical probability is exactly 1/d, regardless of the specific structure ofZd.
Terminology
Summary
Critical Probability of Site Percolation on Zd is 1/d Vertices (sites), open with the smallest probability pH, percolate when they form an infinite open path from graph’s origin v0 Usually, pH values are approximated, but there are a few instances of special lattices with the exact results In finite graph Zd k, d pairs of opposite arcs are k edges away from v0 If there is an open path from v0 to v∈Ak(Zd): k → ∞, Zd percolates
The Definition of Percolation on Zd
The paper defines site percolation on the lattice Zd as the condition where vertices, open with the smallest probability pH, percolate when they form an infinite open path from graph’s origin v0. The structure of the graph is described using basis B(Zd) and integers ai(v) to assign a place to vertex v ∈ Zd k. p. 0 The path length →v = kvk = X d i=1 ai(v) ≤ k ∀v∈Zd k. p. 0 Neighbors of v can be partitioned into d up-step neighbors traversed via ↑i and d down-step neighbors traversed via ↓i. p. 0 The set Ak(Zd) are k-paths build by the up-step traversal. p. 0
Derivation of the Critical Probability Bound
The authors establish an upper bound for the critical probability using two inequalities derived from analyzing path extensions.
-
The first inequality states that after k up-steps, there are d k paths and ψk = (dp)k. p. 0
-
The second inequality shows that one down-step extends (k+2m-2)-paths to (k+2m)-paths, with no more than mdk(k+2m)-paths. p. 0
The limit as k → ∞ leads to the conclusion that ψZd, p < 1/d = 0.
Conclusion on Critical Probability
From inequalities (1) and (2), the paper concludes that pH Zd = 1/d. This result is derived from the initial setup where vertices are open with the smallest probability pH. p. 0 p. 0
Key Mathematical Tools Used
The analysis relies on inductive reasoning to count paths and their extensions. The key steps involve calculating the number of k-paths as d k, leading to the expected number of percolating paths ψk = (dp)k. p. 0 Furthermore, the argument involves bounding the number of possible extensions by relating them to non-percolating paths. p. 0
Reference to External Work
The paper cites Bella Bollobas and Oliver Riordan for a general reference on percolation. The path definition is also referenced in [2]. p. 0
Summary of Findings
The single most informative sentence about the paper's subject and finding is Critical Probability of Site Percolation on Zd is 1/d. This result is derived from the initial setup where vertices are open with the smallest probability pH. The analysis shows that for the lattice Zd, the critical probability is exactly 1/d. p. 0
How the training signal is built
The paper uses a path counting argument to determine percolation, where k-paths are defined by up-step traversals. The expected number of percolating paths ψk is calculated as (dp)k. p. 0 This count is then used to establish the upper bound pH Zd ≤ 1/d (1).
Where the gains come from
The critical probability pH Zd = 1/d is established by combining two inequalities, (1) and (2). Inequality (1) provides an upper bound based on the number of k-paths, and inequality (2) accounts for the extensions via down-steps. p. 0 The final conclusion is that ψZd, p < 1/d = 0 ⇒ pH Zd ≥ 1/d (2).
Pruning redundant reasoning tokens
The derivation involves showing that the number of paths of length k+2m is bounded by mdk(k+2m). This bound is crucial for proving that the expected number of percolating paths vanishes in the limit. p. 0 The entire argument hinges on the inductive counting of paths and their extensions. p. 0
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved Path Finding in Complex Networks: The system can accurately model and predict percolation thresholds for site percolation on Z d lattices, which informs how connectivity (or failure) propagates across structured AI models or neural network architectures that resemble these graphs.
-
Optimized Resource Allocation in Distributed Systems: By understanding the critical probability of site percolation, the system can determine the minimum required connectivity density needed to ensure an infinite open path exists within a distributed computing fabric, leading to more resilient and scalable network designs.
-
Robust Fault Tolerance in Neural Architectures: The derived upper bound pH Z d <= 1/d suggests a fundamental limit on successful connectivity in certain high-dimensional structures, allowing AI developers to design architectures that are inherently resistant to complete disconnection or catastrophic failure modes under specific connectivity constraints.
Related papers
- Existence of a fluid phase for the two-dimensional one-component plasma
- The Huang-Yang conjecture for the low-density Fermi gas
- Anderson localisation in infinite and finite resonator crystals with long-range interactions
- Free energy and spectral edge of the SYK model
- Anderson localization for 1-d quasi-periodic Schr"odinger operators with degenerate weights
- Irregular SLE(4) martingales and isomonodromic deformations