Random walks on graphs with a strong isoperimetric property (Q1099885)

Let K be an infinite connected directed graph and V its set of vertices. Let \(x\sim y\), \(x\in V\), \(y\in V\), denote the existence of an edge in K from x to y. A random walk on K is a Markov chain with state space V and transition matrix p(x,y), x,y\(\in V\), such that \(p(x,y)=0\) if not \(x\sim y\). Assume that the random walk is strongly reversible, i.e. \(m(x)p(x,y)=m(y)p(y,x)\), x,y\(\in V\) with \(0<m(x)\leq M\) and \(m(x)p(x,y)\geq m>0\), \(x\sim y.\) The author proves the equivalence of a number of conditions. We mention: (I): There is a constant \(a>0\) with \(a| L| \leq | \partial L|\) for all finite subgraphs L. Here \(| L|\) is the number of vertices in L and \(\partial L=\{x\in L:\) \(x\sim y\in K-L\}.\) (II): Exponential convergence to zero of the n-step transition probabilities, of order uniform with respect to x and y. (III): The \(L_ r(V,m)\) norm of the operator P with \(Pf(x)=\sum p(x,y)f(y)\) is smaller than 1 for some (and then all) \(r\in (1,\infty).\) (IV): The operator \(G=\sum_{n}P\) n on \(L_ r(V,m)\) is bounded for some (and then all) \(r\in (1,\infty).\) The simple random walk with \(p(x,y)=1/d(x)\) for all y with \(x\sim y\) is strongly reversible with \(m(x)=d(x)=\) degree of x, if \(d(x)\) is bounded.