Cutsets, percolation and random walks
Vienna Probability Seminar
Which graphs $G$ admit a percolating phase (i.e. $p_c(G)<1$)? This seemingly simple question is one of the most fundamental ones in percolation theory. A famous argument of Peierls implies that if the number of minimal cutsets of size $n$ from a vertex to infinity in the graph grows at most exponentially in $n$, then $p_c(G)<1$. Our first theorem establishes the converse of this statement. This implies, for instance, that if a (uniformly) percolating phase exists, then a "strongly percolating one also does. In a second theorem, we show that if the simple random walk on the graph is uniformly transient, then the number of minimal cutsets is bounded exponentially (and in particular $p_c<1$). Both proofs rely on a probabilistic method that uses a random set to generate a random minimal cutset whose probability of taking any given value is lower bounded exponentially on its size. Joint work with Philip Easo and Vincent Tassion.