Introduction
The study of random walks on graphs provides deep insights into the relationship between a network's geometry and its dynamical properties. A central metric in this field is the mixing time—the time required for a random walk to reach its stationary distribution. On a standard $d$-dimensional integer lattice box of side length $n$, it is well-established that the mixing time scales as $\Theta(n^2)$. However, real-world systems often exhibit structural irregularities. This paper investigates whether this scaling behavior persists when the lattice is subjected to random edge removal, a process known as percolation.
The Problem: Robustness Under Perturbation
The authors consider super-critical bond percolation on the $d$-dimensional lattice $\mathbb{Z}^d$. In this model, each edge is retained with probability $p$ and removed with probability $1-p$. When $p$ exceeds a critical threshold $p_c$, an infinite "giant component" emerges. The research focuses on the largest cluster, $C_d(n)$, within a box of size $n$.
The fundamental question is whether the "holes" and "dead ends" created by random edge removal create significant bottlenecks that slow down the mixing process. While the geometry of a percolation cluster is significantly more complex and fractal-like than a standard grid, the authors seek to determine if the global diffusion rate remains fundamentally the same.
Methodological Framework
The proof relies on several advanced probabilistic techniques, most notably the first non-trivial application of the Lovász-Kannan Average Conductance to yield a tight result in this context.
1. Lovász-Kannan Average Conductance
Traditional methods for bounding mixing times often rely on the spectral gap or the Cheeger constant, which looks at the worst-case bottleneck in a graph. However, these can be too sensitive to local irregularities in random graphs. The Lovász-Kannan method uses a weighted average of conductance across sets of different sizes, providing a more robust tool for establishing tight bounds in disordered environments.
2. Renormalization and Bootstrap Techniques
To bridge the gap between local randomness and global behavior, the authors employ a renormalization argument. By partitioning the lattice into blocks and identifying "good" blocks that satisfy specific connectivity properties, they show that the large-scale structure of the cluster mimics that of the original lattice. A bootstrap technique is further used to ensure that geometric estimates hold even when the complement of a set of vertices is disconnected.
3. Planar Analysis ($d=2$)
For the two-dimensional case, the authors utilize the properties of the dual graph and results from first-passage percolation. This allows them to bound the boundary sizes of sets by analyzing path lengths in the random environment.
Key Findings
The paper establishes that for $d \ge 2$ and $p > p_c$, the mixing time $\tau_1$ on the largest cluster $C_d(n)$ is indeed $\Theta(n^2)$ with high probability as $n \to \infty$.
- Isoperimetric Stability: The results show that the Cheeger constant $\phi(C_d(n))$ is $\Theta(n^{-1})$, matching the order of magnitude of the unperturbed lattice. This implies that the "Swiss cheese" geometry of the percolation cluster still satisfies a lattice-like isoperimetric inequality.
- Tightness: The authors provide matching upper and lower bounds, confirming that the mixing time is robust up to a constant factor. The global "flow" of the random walk is not fundamentally hindered by the random removal of edges, provided the graph remains globally connected.
Limitations and Future Directions
While the scaling law $\Theta(n^2)$ is robust, the constants associated with these bounds depend on the edge probability $p$. The behavior of these constants as $p$ approaches the critical threshold $p_c$ remains an open area of inquiry. Furthermore, the critical regime ($p = p_c$) presents a much more challenging problem, as the cluster becomes highly fractal and "spindly," likely leading to much slower mixing.
The techniques developed here also suggest potential applications to other random graph models, such as Erdős-Rényi graphs $G(n, c/n)$, where mixing times are expected to be poly-logarithmic in $n$.
Summary updated