The critical value of percolation on Cayley graphs. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T08:22:08Z http://mathoverflow.net/feeds/question/87788 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/87788/the-critical-value-of-percolation-on-cayley-graphs The critical value of percolation on Cayley graphs. Kate Juschenko 2012-02-07T11:05:30Z 2012-02-09T23:46:47Z <p>Let $\Gamma$ be a discrete group with a generating set $S$. Let $p_c(\Gamma,S)$ be the critical probability for percolation of the Cayley graph of $\Gamma$. Is it known that if $\Gamma$ is non-amenable then there exists a generating set $S$ such that $p_c(\Gamma,S)&lt;\frac{1}{2}$ (or some other constant)? </p> <p>The details on the question:</p> <p>Let <code>$0&lt;p&lt;1$</code> , the Bernoulli bond percolation of the Cayley graph defined as follows: the edge is open with probability $p$ and closed with $1-p$. The connected components of the graph are those that spanned by open edges. Let $\theta(p)$ be the probability that the origin belongs to an infinite open component. Then $p_c(\Gamma, S)=\sup (p:\theta(p)=0)$.</p> http://mathoverflow.net/questions/87788/the-critical-value-of-percolation-on-cayley-graphs/87790#87790 Answer by Vincent Beffara for The critical value of percolation on Cayley graphs. Vincent Beffara 2012-02-07T11:53:31Z 2012-02-07T11:53:31Z <p>No need for non-amenability for that. Essentially, if for <em>some</em> generating set $S$ you have $p_c(\Gamma,S)&lt;1$, then replacing $S$ by the $S$-ball $S_k$ of radius $k$, one always has $p_c(\Gamma,S_k) \to 0$ as $k \to \infty$.</p> <p>Admittedly $S_k$ has some multiplicity issues, which you might want to rule out, but the gist of it is, if the degree of the Cayley graph becomes huge, the critical point will become very small, the only obstruction being if your group is virtually $\mathbb Z$.</p> http://mathoverflow.net/questions/87788/the-critical-value-of-percolation-on-cayley-graphs/87949#87949 Answer by Asaf Nachmias for The critical value of percolation on Cayley graphs. Asaf Nachmias 2012-02-09T01:26:47Z 2012-02-09T01:26:47Z <p>In the non-amenable case the cheeger constant of $(\Gamma, S_k)$ goes to infinity with $k$ (with or without multiplicities) and this implies $p_c$ tends to $0$ by the standard exploration argument, see Theorem 2 of <a href="http://www.springerlink.com/content/t5l8401n32262112/fulltext.pdf" rel="nofollow">http://www.springerlink.com/content/t5l8401n32262112/fulltext.pdf</a></p> http://mathoverflow.net/questions/87788/the-critical-value-of-percolation-on-cayley-graphs/87954#87954 Answer by Louigi Addario-Berry for The critical value of percolation on Cayley graphs. Louigi Addario-Berry 2012-02-09T02:52:14Z 2012-02-09T15:49:52Z <p>In a paper called <a href="http://www.math.bme.hu/~balint/oktatas/perkolacio/percolation_papers/benjamini_lyons_peres_schramm_nonamen.pdf" rel="nofollow">Critical Percolation on any Nonamenable Group Has no Infinite Clusters</a>, Benjamini, Lyons, Peres, and Schramm show that ... critical percolation on any nonamenable group has no infinite clusters. </p> <p>More precisely, if $G$ is a Cayley of any finitely generated non-amenable group, then $\theta(p_c)=0$. This immediately implies that $p_c(G) &lt; 1$. </p> <p>The paper also shows that for any invariant bond percolation $P$&nbsp; on $G$ (invariant means its distribution is unchanged by the action of the group), if in $P$&nbsp; the expected number of neighbours of the origin $o$ is at least <code>$d_G(o) - \kappa(G),$</code> then with probability one there is percolation. (Here $d_G(o)$ is the number of neighbours of the origin in $G$, and $\kappa(G)$ is the Cheeger constant of $G$, which is positive since the group is non-amenable.) This gives that <code>$p_c(G) \le 1-\kappa(G)/d_G(o),$</code> which is weaker than the bound in Vincent Beffara and Asaf Nachmias' answers, but applies to a broader range of percolation models. </p> http://mathoverflow.net/questions/87788/the-critical-value-of-percolation-on-cayley-graphs/88050#88050 Answer by Ori Gurel-Gurevich for The critical value of percolation on Cayley graphs. Ori Gurel-Gurevich 2012-02-09T23:46:47Z 2012-02-09T23:46:47Z <p>Here's a more direct argument:</p> <p>Let $S$ be a generating set and let $s\in S$. Pick some $x_1,x_2,\ldots , x_k$ such that all of the $x_i$'s and $x_i^{-1}s$ are different from each other and are not in $S$. Do the same for all $s\in S$ in such a way that all of these elements are distinct. Let $S'$ be the resulting set.</p> <p>Now, $p_c(\Gamma,S')$ is small. Why? because we may think of percolation on $Cayley(\Gamma,S')$ as inducing a percolation on $Cayley(\Gamma,S)$, except that now the probability of some $a$ and $as$ being connected is at least $(1-(1-p^2)^k)$ since they may be connected through any pair $x_i$ and $x_i^{-1}s$, there are $k$ such pairs and each has a probability of $p^2$ being open. This immediately show that $p_c$ goes to 0 with $k$.</p>