Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)<\frac{1}{2}$ (or some other constant)?

The details on the question:

Let $0<p<1$ , 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)$.

share|improve this question
    
Could you define the term `critical probability for percolation'? –  HJRW Feb 7 '12 at 11:15
    
HW: sure, above... –  Kate Juschenko Feb 7 '12 at 11:27
add comment

4 Answers

up vote 5 down vote accepted

Here's a more direct argument:

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.

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$.

share|improve this answer
    
How do you precisely induce percolation on $Cayley(\Gamma,S')$ to $Cayley(\Gamma,S)$? –  Mikael de la Salle Feb 11 '12 at 12:50
    
From every $a$ there are now $k$ disjoint paths of length 2 leading to $as$, passing through $ax_i$, $i=1,\ldots,k$. So we look at the percolation on $Cayley(\Gamma, S')$ and if any of these paths is open, we open the corresponding edge $(a,as)$ in the percolation on $Cayley(\Gamma,S)$. –  Ori Gurel-Gurevich Feb 11 '12 at 19:47
    
Thank you, everything is clear now. –  Mikael de la Salle Feb 13 '12 at 9:55
    
I think this is the most direct proof. I would prefer to accept this as an answer to the question. Thank you everyone for sharing the ideas and proofs! –  Kate Juschenko Feb 13 '12 at 15:36
add comment

No need for non-amenability for that. Essentially, if for some generating set $S$ you have $p_c(\Gamma,S)<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$.

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$.

share|improve this answer
2  
right, but the point is that your Sk has multiplicities... I don't know how to get rid of them –  Kate Juschenko Feb 7 '12 at 12:46
    
what is the current stage of the question where multiplicity of edges is not allowed? –  Kate Juschenko Feb 7 '12 at 12:53
add comment

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 http://www.springerlink.com/content/t5l8401n32262112/fulltext.pdf

share|improve this answer
1  
Thanks. Could you please explain why we can assume that $S_k$ can be taken without multiplicities? –  Kate Juschenko Feb 9 '12 at 14:33
    
I don't quite see why the cheeger constant will be as large as we want... –  Kate Juschenko Feb 9 '12 at 14:34
add comment

In a paper called Critical Percolation on any Nonamenable Group Has no Infinite Clusters, Benjamini, Lyons, Peres, and Schramm show that ... critical percolation on any nonamenable group has no infinite clusters.

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) < 1$.

The paper also shows that for any invariant bond percolation $P$  on $G$ (invariant means its distribution is unchanged by the action of the group), if in $P$  the expected number of neighbours of the origin $o$ is at least \[ d_G(o) - \kappa(G), \] 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 \[ p_c(G) \le 1-\kappa(G)/d_G(o), \] which is weaker than the bound in Vincent Beffara and Asaf Nachmias' answers, but applies to a broader range of percolation models.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.