Abstract
In percolation theory, the critical probability $p_c$ marks the transition between local and global connectivity. This paper resolves two significant conjectures regarding the geometric characterization of $p_c$ for site percolation on infinite, locally finite graphs. We prove that Kahn’s vertex-cut characterization holds universally for such graphs. Conversely, we disprove the Lyons-Peres edge-cut characterization for site percolation by constructing a specific bipartite graph counterexample where the edge-cut formula significantly underestimates the true threshold.
Introduction
Percolation theory examines how local random processes—such as the "opening" of vertices or edges with probability $p$—lead to large-scale connectivity. In site percolation, vertices are independently open with probability $p$. The critical probability $p_c^{site}$ is the threshold above which an infinite connected component of open vertices exists with probability one.
A long-standing goal has been to characterize $p_c$ using the graph's intrinsic geometry, specifically through cutsets. A cutset is a set of elements (vertices or edges) whose removal disconnects a starting point from infinity. Two primary conjectures have guided this search:
- Kahn’s Conjecture (2003): Characterizes $p_c$ via vertex cutsets.
- Lyons-Peres Conjecture (2016): Characterizes $p_c$ via edge cutsets.
While previously established for bounded-degree graphs, their validity for general locally finite graphs (where vertices can have arbitrarily many neighbors) remained an open question.
Proving Kahn’s Vertex-Cut Conjecture
The author establishes that Kahn’s vertex-cut characterization, $p'_{cut,V} = p_c^{site}$, holds for every locally finite, connected, infinite graph. The proof adapts the "differential inequalities" method, which typically relies on a boundary influence function $\phi_p(S)$.
The technical breakthrough involves a refined definition of this influence function. In standard proofs for bounded-degree graphs, one might count the expected number of open paths to a boundary. However, on general graphs, a single vertex with a massive degree can exert disproportionate influence. By redefining the boundary influence to focus on boundary vertices with at least one neighbor connected to the origin, the author ensures the proof remains robust even as vertex degrees grow without bound. This confirms that vertex cutsets are the natural geometric dual to site percolation.
Disproving the Lyons-Peres Edge-Cut Characterization
While edge cutsets are effective for bond percolation, this paper demonstrates they are insufficient for site percolation on general graphs. The author provides a constructive disproof of the Lyons-Peres conjecture for $p_c^{site}$.
The counterexample is a bipartite graph featuring an "exploding" number of edges between successive layers. In this construction, the number of edges grows exponentially, which causes the edge-cut formula ($p'_{cut,E}$) to predict a relatively low threshold (approximately $0.707$). However, because site percolation is constrained by the state of individual vertices, these vertices act as bottlenecks that the edge-cut formula fails to "see." In the constructed graph, the actual critical probability $p_c^{site}$ is $1$, meaning an infinite cluster never forms for any $p < 1$. This discrepancy proves that the Lyons-Peres characterization is not universal for site percolation.
Conclusion and Implications
This work clarifies the relationship between graph geometry and percolation thresholds. By proving Kahn's conjecture, the paper establishes vertex cutsets as a universal tool for understanding site percolation. By disproving the Lyons-Peres conjecture in this context, it highlights a fundamental difference between site and bond percolation: edge-based metrics cannot always account for the vertex-level bottlenecks inherent in site-based processes. While the Lyons-Peres characterization remains vital for bond percolation, its application to site percolation is strictly limited to bounded-degree environments.
Summary updated