🔢 mathematics

Loop vs. Bernoulli percolation on trees: strict inequality of critical values

This paper investigates loop ensembles on locally finite rooted trees induced by Poisson processes of links, demonstrating that while the critical threshold for infinite loops strictly exceeds that of the underlying Bernoulli link percolation on Galton-Watson trees with finite mean offspring, the two thresholds coincide at zero under heavy-tailed offspring distributions in the random interchange case.

Original authors: Andreas Klippel, Benjamin Lees, Christian Mönch

Published 2026-07-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andreas Klippel, Benjamin Lees, Christian Mönch

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a giant, infinite family tree where every person (or vertex) has a certain number of children. Now, picture this tree not just as a static drawing, but as a busy highway system where "links" (like tiny, invisible roads) appear randomly on the branches. Sometimes, these links are just simple bridges; other times, they are magical portals that swap travelers around or send them on wild detours.

This paper is about a high-stakes game of "connect the dots" played on these trees. The players are trying to see if they can build an infinite path that never ends. There are two ways to play:

The Link Game (Bernoulli Percolation): This is the simple version. You just need one link on a branch to keep the road open. If you have enough links, you can drive forever.
The Loop Game (Loop Percolation): This is the fancy, tricky version. Here, the links are "crosses" or "bars" that act like traffic cops. They don't just let you pass; they might force you to turn around, swap places with someone else, or take a detour that loops back on itself. To have an infinite path here, you don't just need a road; you need a road that doesn't get you stuck in a loop or sent back to the start.

The Big Surprise: The Rules Change Based on the Tree

The authors, Andreas Klippel, Benjamin Lees, and Christian Mönch, discovered that the relationship between these two games depends entirely on how "wild" the family tree grows.

Scenario 1: The Well-Behaved Tree (Finite Mean)
Imagine a tree where, on average, every person has a predictable, finite number of children (say, 3 or 4).

The Finding: In this case, the Loop Game is much harder to win than the Link Game.
The Analogy: Think of the Link Game as a straight highway. You just need a few open lanes to drive forever. But the Loop Game is like driving that same highway, but every few miles, a mischievous elf jumps out and forces you to take a 10-mile detour that might send you back to where you started.
The Result: The paper proves mathematically that you need significantly more links (a higher "threshold") to create an infinite loop than you do to create an infinite link cluster. The "elf" (the loop mechanism) cuts off your path more often than you'd expect. The critical value for loops is strictly larger than the critical value for links. It's not a tiny difference; it's a real, proven gap.

Scenario 2: The Wild, Heavy-Tailed Tree (Infinite Mean)
Now, imagine a tree where most people have no children, but a few lucky (or unlucky) people have thousands or even millions of children. The average number of children is so huge it's effectively infinite.

The Finding: Here, the two games become identical, but only under a specific condition.
The Analogy: In this chaotic forest, if the "tail" of the distribution is heavy enough (meaning the rare, super-fertile individuals are frequent enough to satisfy a precise mathematical condition), the "elves" (the loop rules) are overwhelmed by the sheer number of branches. They can't stop you. If there's a road open (a link), the loops can find a way through. The "cutting" mechanism that worked in the well-behaved tree fails here.
The Result: The paper shows that for these specific heavy-tailed trees, the threshold for both games drops to zero. This means that even with a tiny, almost non-existent number of links, there is a positive probability of finding an infinite path in both the simple Link Game and the complex Loop Game. They coincide at zero, but it's a probabilistic guarantee, not an absolute certainty for every single tree realization.

What They Ruled Out

The paper explicitly argues against the idea that the two games are always the same.

Not Always Equivalent: While some previous work on complete graphs (where everyone is connected to everyone) showed that the two games behave the same, this paper proves that on trees, they are usually different.
No "Free Lunch": You cannot assume that just because you have an infinite cluster of links, you automatically have an infinite loop. In the "well-behaved" tree scenario, the loop mechanism actively destroys infinite paths that the link game would preserve.

How Sure Are They?

The authors are extremely confident. They didn't just run computer simulations or guess; they proved these results with rigorous mathematics.

For the "well-behaved" trees, they used a "deterministic pruning criterion." Think of this as a mathematical rulebook that says, "If you see this specific pattern of loops cutting off branches, you know for a fact the infinite path is gone." They proved this happens often enough in these trees to guarantee the gap between the two games.
For the "wild" trees, they used probability theory to show that if the tail of the offspring distribution is heavy enough, the "cutting" mechanism simply cannot keep up with the explosion of branches, forcing the thresholds to meet at zero.

The Takeaway

The paper solves a long-standing puzzle about how randomness and structure interact. It tells us that the shape of the world (the tree) dictates the rules of the game.

In orderly worlds (finite average children), complexity (loops) creates a barrier, making infinite paths harder to find than simple connections.
In chaotic worlds (heavy-tailed children), the sheer scale of the structure overwhelms the complexity, making infinite paths just as easy to find as simple connections—provided the chaos is "heavy" enough to meet the specific mathematical criteria.

It's a beautiful reminder that in the world of math, the answer to "how hard is it to get from A to infinity?" depends entirely on how the map is drawn.

Technical Summary: Loop vs. Bernoulli Percolation on Trees

Problem Statement
This paper investigates the relationship between two critical parameters on locally finite rooted trees: the threshold for the existence of infinite loops in a random loop model ( $\beta_{\text{loop}}^c$ ) and the threshold for the existence of an infinite cluster in the induced Bernoulli link percolation ( $\beta_{\text{link}}^c$ ).

The random loop model generalizes the random interchange process (random stirring) and representations of quantum spin systems. In this model, edges carry independent Poisson processes of "links" (crosses or bars). A necessary condition for an infinite loop to exist is that the set of edges carrying at least one link forms an infinite connected component (link percolation). While this condition is sufficient on dense graphs like the complete graph (Schramm [25]) and the hypercube, it is known to be insufficient on bounded-degree infinite graphs (Mühlbacher [22]). The central question addressed is how the geometry of the underlying tree—specifically the offspring distribution of Galton–Watson trees—affects the gap between these two thresholds.

Methodology
The authors employ a combination of probabilistic coupling, potential theory on trees, and large-deviation estimates.

Coupling and Pruning: The core technical innovation is a coupling between the loop model and a "delayed pruning percolation" on the link cluster. The authors define a local "pruning" event where specific configurations of links (e.g., exactly two crosses on a child edge and one on the parent) force the loop trajectory to backtrack, effectively cutting off infinite descendant subtrees from the root loop.
- They construct a deterministic criterion (Theorem 4.1) based on "weighted pruning." If the frequency of these pruning events along infinite rays is sufficiently high, the loop cluster becomes subcritical even if the link cluster is supercritical.
- This is formalized using a "delayed" version of the pruning to ensure independence between local events by spacing them modulo 3 in the tree depth.
Potential Theory: To analyze the survival of the pruned process, the authors utilize the connection between percolation and the capacity of the tree boundary ( $\partial T$ ). They employ Lyons' capacity criterion and the concept of the branching number ( $\text{br}(T)$ ). The critical link threshold is characterized by the branching number, while the loop threshold is determined by whether the "weighted branching number" of the set of rays with low pruning density is strictly smaller than the tree's branching number.
Galton–Watson Analysis:
- Finite Mean Case: For trees with finite mean offspring $m$ , the authors use large-deviation estimates (Chernoff bounds) on the size-biased Galton–Watson measure to show that the set of rays with "bad" (low pruning) density has a strictly smaller relative branching number than the tree itself.
- Heavy-Tail Case: For trees with infinite mean offspring satisfying a specific tail condition, the authors analyze the annealed (averaged) critical values. They construct an auxiliary Galton–Watson tree representing the "one-cross" skeleton of the loop model to show that for sufficiently heavy tails, the loop and link thresholds coincide at zero.

Key Contributions and Results

The paper establishes two complementary theorems regarding the separation or coincidence of critical values on Galton–Watson trees:

Theorem A (Strict Inequality for Finite Mean): For a supercritical Galton–Watson tree with finite mean offspring $m \in (1, \infty)$ , conditioned on survival, the loop critical value is strictly larger than the link critical value almost surely:
$\beta_{\text{loop}}^c(T) > \beta_{\text{link}}^c(T) = -\log(1 - m^{-1})$
This result holds for any loop parameter $u \in [0, 1]$ . The proof relies on the deterministic weighted pruning criterion, demonstrating that local loop configurations act as a "cutting mechanism" that renders the effective branching number of the loop cluster subcritical even when the link cluster is supercritical.
Theorem B (Coincidence for Heavy Tails): In the crosses-only model ( $u=1$ ), if the offspring distribution has a sufficiently heavy tail such that $\liminf_{\varepsilon \downarrow 0} \sqrt{\varepsilon} f'(1-\varepsilon) > 1/\sqrt{2}$ (where $f$ is the probability generating function), then the annealed critical values coincide at zero:
$\beta_{\text{loop}, \text{ann}}^c(\zeta) = \beta_{\text{link}, \text{ann}}^c(\zeta) = 0$
This applies to offspring laws with power-law decay $\zeta_k \sim k^{-\tau}$ where $\tau \in (1, 3/2)$ . In this regime, the heavy tails of the tree structure dominate the local loop constraints, making the necessary condition (link percolation) effectively sufficient in the annealed sense.

Significance and Claims
The authors claim that these results provide a sharp dichotomy in the behavior of loop percolation on random trees, distinguishing between "sparse" trees with finite mean and those with "heavy-tailed" infinite mean.

Separation Mechanism: The paper identifies a specific local mechanism (pruning via backtracking) that creates a gap between link and loop thresholds. This gap is robust for finite-mean trees because the probability of encountering the necessary local configurations is high enough to suppress infinite loops, even when infinite link clusters exist.
Boundary Dimension: The results support a broader conjecture that the equality of critical values is tied to the dimension of the tree boundary. For finite-mean trees, the boundary has finite positive dimension, and the thresholds separate. For heavy-tailed trees, the boundary dimension effectively diverges (or the structure becomes dense enough in the annealed sense), leading to the coincidence of thresholds.
Generality: The framework unifies the random interchange process and quantum spin system representations (XXZ models) under a single loop percolation analysis, extending previous results on regular trees and complete graphs to the more complex setting of random trees with quenched disorder.

The paper concludes that whether percolation is a sufficient condition for infinite loops depends fundamentally on the interplay between the local loop dynamics and the global geometric structure (branching number and boundary dimension) of the underlying tree.

The Big Surprise: The Rules Change Based on the Tree

What They Ruled Out

How Sure Are They?

The Takeaway

More like this