Isoperimetric criterion for bounded percolation thresholds

About 25 years old · traced to

Let GG be a finite graph and define

δ(G)=sup⁡{α:∣∂S∣≥∣S∣α for all S⊂G, ∣S∣≤∣G∣/2}.\delta(G)=\sup\{\alpha:|\partial S|\geq |S|^\alpha\text{ for all }S\subset G, \ |S|\leq |G|/2\}.

Here ∂S\partial S is the vertex boundary used in the paper, and pGp^G is the percolation threshold. Isoperimetric-threshold conjecture. If δ(G)>δ>0\delta(G)>\delta>0, then there is a function ff such that pG<f(δ)<1p^G<f(\delta)<1. This is proposed as a sharpening of an earlier theorem and is left open.

References

Primary source

Itai Benjamini, “percolation on finite graphs”, arXiv:math/0106022 (2001).

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 0

No solutions have been posted yet.