← All problems

Cheeger constant and the percolation nonuniqueness phase

13 years old · traced to

Let G=(V,E)G=(V,E) be an infinite, connected, locally finite, vertex-transitive graph. In Bernoulli bond percolation with parameter p∈[0,1]p\in[0,1], each edge is retained independently with probability pp; write N∞N_\infty for the number of infinite connected components of the retained subgraph and Pp\mathbb P_p for its law. Define the critical and uniqueness thresholds by

pc(G)=inf⁡{p∈[0,1]:Pp(N∞>0)=1},pu(G)=inf⁡{p∈[0,1]:Pp(N∞=1)=1}.p_c(G)=\inf\{p\in[0,1]:\mathbb P_p(N_\infty>0)=1\},\qquad p_u(G)=\inf\{p\in[0,1]:\mathbb P_p(N_\infty=1)=1\}.

For a nonempty finite vertex set K⊆VK\subseteq V, let ∂EK\partial_E K be the set of edges with exactly one endpoint in KK, and define the (normalized) Cheeger constant by

h(G)=inf⁡K⊆V finite, nonempty∣∂EK∣∑v∈Kdeg⁡(v).h(G)=\inf_{\substack{K\subseteq V\text{ finite, nonempty}}} \frac{|\partial_E K|}{\sum_{v\in K}\deg(v)}.

The question is whether, for every such GG,

pc(G)<pu(G)⟺h(G)>0.p_c(G)<p_u(G)\quad\Longleftrightarrow\quad h(G)>0.

Percolation on Hyperbolic Graphs Percolation at the uniqueness threshold via subgroup relativization

Background

The equivalence is the vertex-transitive case of the Benjamini–Schramm conjecture, formulated in 1996 for connected, locally finite, quasi-transitive graphs. Here quasi-transitive means that the automorphism group has finitely many vertex orbits; vertex-transitive graphs are a special case. The conjecture connects a geometric isoperimetric condition—positive Cheeger constant, or nonamenability—to the existence of a parameter interval with infinitely many infinite clusters. On amenable graphs, the Burton–Keane uniqueness argument rules out that interval; Gandolfi, Keane, and Newman extended the argument to amenable quasi-transitive graphs. Percolation on Hyperbolic Graphs Non-uniqueness and mean-field criticality for percolation on nonunimodular transitive graphs

The first transitive examples with pc<pup_c<p_u came from Grimmett and Newman’s work on products of regular trees with Euclidean lattices: they established separation when the tree degree is sufficiently large. This helped motivate the broader conjecture, but such perturbative examples do not settle the general implication from nonamenability. Subsequent work has combined geometric, combinatorial, and probabilistic methods to prove separation for broader, but still restricted, classes. Non-uniqueness and mean-field criticality for percolation on nonunimodular transitive graphs

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 1

Claimed by OpenAI. For every infinite connected locally finite nonamenable quasi-transitive graph, the manuscript claims p_c<p_{2->2}<=p_u for Bernoulli bond percolation, yielding an interval with infinitely many infinite clusters. On vertex-transitive graphs this addresses the positive-Cheeger-constant implication in the page’s equivalence. The converse implication and graphs outside the stated locally finite setting are not established by this claim.See full solutionHide full solution