A note on rough isometry invariance of resistance

András Telcs IMC Graduate School of Business, Budapest Zrínyi u. 14, Budapest, H-1051 Hungary

                e-mail:telcsa@imc.hu

October 24, 2001

Abstract In this note it is shown that resistance and resistance dimension is

rough isometry invariant.

1 Introduction

It was shown by Kanai [K] that RWs two roughly isometric graphs are of the same type, i.e. both are recurrent or transient. In general recurrence is one of the first question to study with respect of a new problem on random walks. This is the case with rough isometry as well. The present paper goes further and shows that the resistance and the resistance dimension is invariant under the rough isometry between graphs. The presented proof is simple, it uses only combinatorial and probabilistic methods while it is possible that operator comparison techniques would be an alternative way. Recently rough isometry is heavily investigated, p-harmonic functions are studied by Holopainen [H], Holopainen and Soardi [HS] and related problems on groups by Pittet and Saloff-Coste [PS](c.f. [L] and [B],[BS] as well). For further literature Woess’ book [W] is a good starting point.

Definition 1.1 Two graphs G = (V, E) and G′ = (V′, E′) are roughly isometric ( denoted by G ≍ G′ )

if there is a mapping Ψ : V → V′ and constants L > 0, λ > 0 such that

λd(x, y) − L ≤ d (φ(x), φ(y)) ≤ λ^{−1}d(x, y) + L

for all x, y ∈ V, where d(., .) is the usual graph distance.

and for all x′ ∈ V′

d′ (x′, φ(V)) ≤ L.

Consider the graph edges as unit resistors and then ”measure ” the resistance between vertices or sets The result of the paper can be easily generalized to general resistances. The formal definition of the resistance between sets can be given via the Dirichlet form.

Definition 1.2 For A, B ⊂ V, d(A, B) > 0

R(A, B)^{−1} = inf_{f} ∑_{(x,y)∈E}(f(x) − f(y))^{2},

where the infimum is taken over the functions f ≡ 1 on A and f ≡ 0 on B.

Let us consider a reference vertex o ∈ V and define G^{N} = G^{o,N}, the subgraph induced by B(o, N) for an N ∈ ℕ. From the monotonicity law (c.f. [DS]) it follows that R^{N} the resistance on G^{N} bigger or equal then R and it is easy to see that

lim_{N→∞} R^{N} = R.  (1.1)

Definition 1.3 A graph is locally finite if there is a D > 0 such that all x ∈ V the vertex degree d(x) = |{y : (x, y) ∈ E)}| ≤ D.

For shortness a_{n} ≍ b_{n} will denote that there is a constant c > 1 for which c^{−1} < \frac{a_{n}}{b_{n}} < c for all possible n.

Our result is the following.

Theorem 1.1 If G ≍G′ locally finite graphs then there is an L > 1, such that for all A, B ⊂ V finite sets (assuming that d(A, B) > L then

R(A, B) ≍ R′ (φ(A), φ(B)) .

Remark 1.1 The proof of this result is based on some natural and beautiful ideas of Doyle and Snell [DS], particularly it uses the shorting and cutting method, monotonicity principle and the K-fuzz of graphs. These are the main ingredients of a possible other proof as well which establishes a general Dirichlet form comparison between roughly isometric graphs (Theorem 3.10 of [W]). Based on Theorem 3.10 and Corollary 3.6 of [W] the above theorem can be seen easily. One can observe that both approaches based on the same ideas, while the present proof is slightly more elementary then the proof of Theorem 3.2 which implies Corollary 3.6.

The proof of the result uses the nice analogy between electric networks and reversible Markov chains or more particularly random walks on weighted graphs (c.f. [DS]). Here we consider the simplest (un-weighted) case, nearest neighbor random walk X_{n} on G, where P (X_{n+1} = y|X_{n} = x) = p_{x,y} = \frac{1}{d(x)} if (x, y) ∈ E.

A formally special case of the above theorem has particular importance. Denote

B_{x,N} := {z : d(x, z) ≤ N}

and

S_{N,k} = B_{x,N}\B_{x,N−1}.

Corollary 1.2 For any x ∈ V, and any N, M > 0, M > N + 2K

R(S_{x,N}, S_{x,M}) ≍ R (φ(S_{x,N}x), φ(S_{x,M})) .

It is well known that the volume growth is rough isometry invariant, but from the above result it follows, that the resistance dimension is rough isometry invariant too.

Definition 1.4 The resistance dimension is d_{Ω} if there is a A > 1 such that

2 − d_{Ω} = lim sup_{R→∞} \frac{R(S_{x,R}, S_{x,AR})}{log R}.  (1.2)

Corollary 1.3 If G ≍ G′ then

d_{Ω} = d′_{Ω}.

As one can find that (c.f. [GT],[T2]) these results have far reaching consequences to random walks on graphs. The proof of this corollary is straightforward from Corollary 1.2 with the proper choice of A′ depending on A, λ, K.

2 Proof of the result

Definition 2.1 \overline{G}^{K} = (V, \overline{E}^{K}) is K-fuzz of a graph G if the vertex set is the same and (x, y) ∈ \overline{E}^{K} if d(x, y) ≤ K.

Lemma 2.1 If G ≍ G′ and φ is the mapping from G to G′ then there is a K > 1 for

R(A, B) ≥ c\overline{R′}^{K} (φ(A), φ(B))

for any A, B ⊂ V.

Proof. Let us choose N big enough to ensure that

A ∪ B ⊂ B(o, N − 2L)

and restrict our attention to G^{N}. We shall prove the statement for R^{N} which implies (2.3) using (1.1). To avoid cumulating superscripts we suppress N in the notations. Let us consider first the minimal set W ⊂ V of vertices which representing the equivalent classes of vertices projected to the same image. This means that φ(W) = φ(V) and for all x, y ∈ W : φ(x) ≠ φ(y). Let us introduce W′ = φ(V) and decompose φ = P ∘ C, such that C : V ↦ W is collapsing the equivalence classes and P : W → W′ is a bijection. Thanks to the definition of rough isometry and the boundedness of the vertex degree one equivalence class contains at most M = ⌊λ^{−1}L⌋^{D−1}vertices. Let us define a new graph G_{W} = (W, E_{W}) on W where (x, y) ∈ E_{W} if there is a (s, t) ∈ E such that φ(s) = x, φ(t) = y. Denote R_{W} the resistance on G_{W} . It is clear that in this way at most M^{2} edges projected to (x, y). From the monotonicity law it follows that

R(A, B) ≥ \frac{1}{M^{2}} R_{W} (C(A), C(B)).

If (x, y) ∈ E_{W} then

d′(P (x), P (y)) ≤ λ^{−1} max_{s∈C^{−1}(x),t∈C^{−1}(y)} d(s, t) + L

≤ λ^{−1} max_{s∈C^{−1}(x),t∈C^{−1}(y)} (d(s, x) + d_{W} (x, y) + d(y, t)) + L

≤ λ^{−1}(2λ^{−1}L + 1)) + L =: K,

which means that (P (x), P (y)) ∈ \overline{E′}^{K} i.e. edge in the K− fuzz of G_{W′}. From this it follows that

R_{W} (C(A), C(B)) ≥ \overline{R}_{W′}^{K}(φ(A), φ(B)) ≥ \overline{R′}^{K}(φ(A), φ(B)).

Lemma 2.2 For a locally finite graph G there are constants K, c > 1 such that for any infinite sets A, B ⊂ V, d(A, B) > K

R(A, B) ≤ c\overline{R}^{K} (A, B) .  (2.3)

Proof. We modify G by contracting A and B into single vertices a and b. The new graph has the edges (on V \(A∪B) ) of the old one which are disjoint of A and B, and a (and b ) connected to all the vertices which had neighbors in A (and B). It is clear that this operation can not increase the resistance between any two sets (c.f. monotonicity law in [DS]). It is evident that R(A, B) = R(a, b) since the resistances influenced only by the edges between the sets. The random walk on the new graph is again the simple nearest neighbor walk on the graph. With a slight abuse of the notation we shall use P for the probabilities of the random walk reflected on A and killed in B on the finite graph G^{o,N} (c.f. remark in the proof of Lemma 2.1 and assume that N is enough large.) Let us start with the observation borrowed from [DS] or [T1].

R(A, B) = R(a, b) = \frac{1}{d(a)} ∑_{i} P (X_{i} = a, i < T_{b}) ,

where T_{b} = min{i : X_{i} = b}. Following the idea of [DS] the RW on the K-fuzz of G (denote by \overline{G}^{K}) evolves by the law

\overline{P}^{K} = \frac{P + P^{2} + ...P^{K}}{K} ,

i.e. it takes steps of length 1,2,.. K with equal probability with respect to the appropriate power of P. From this it follows that for a given trajectory of X_{n} a random time decimation can define \overline{X}_{k} = \overline{X}_{k}^{K} the fuzz walk. Formally \overline{X}_{0} = X_{0}, the uniform waiting time τ_{1} and \overline{X_{1}} = X_{τ_{1}}, and than τ_{_{2},}\overline{X_{2}}...respectively. One should observe that for i ∈ [τ_{j}, t_{j+1})

\{X_{i} = 0\} ⊂ \{\overline{X}_{j}^{K} ∈ B_{0,K}\},
P (X_{i} = a, i < T_{b}) = P (X_{i} = a, \overline{X}_{j} ∈ B_{a,K}, i < T_{b}, i ∈ [τ_{j}, t_{j+1})) (2.4)

=∑_{z∈B_{a,K}} P (X_{i} = a, \overline{X}_{j} = z, i < T_{b}, i ∈ [τ_{j}, t_{j+1}))

= ∑_{z∈B_{a,K}} P (X_{i} = a, \overline{X}_{j} = z, i < T_{b}, i ∈ [τ_{j}, t_{j+1})) \frac{\overline{P}^{K}(z,a)}{\overline{P}^{K}(z,a)}

≤ C\overline{P}^{K} (\overline{X}_{j+1} = a, j + 1 < \overline{T_{b}}, i ∈ [τ_{j}, t_{j+1})) , where the estimate \overline{P}^{K}(z, a) ≥ c was used. Finally summing (2.4) for i the

∑_{i=k}^{∞} P (X_{i} = a, i < T_{b}) ≤ C ∑_{i=0}^{∞} ∑_{j=0}^{∞} P (\overline{X}_{j+1} = a, j + 1 < \overline{T_{b}}, i ∈ [τ_{j}, t_{j+1}))

which results

∑_{i=0}^{∞} P (X_{i} = a, i < T_{b}) ≤ KC ∑_{j=0}^{∞} P (\overline{X}_{j} = a, j < \overline{T_{b}}) .

Finally

R(A, B) = \frac{1}{d(a)} ∑_{i=0}^{∞} P (X_{i} = a, i < T_{b})

≤ \frac{C}{d(a)} ∑_{j=0}^{∞} P (\overline{X}_{j} = a, j < \overline{T_{b}})

= C \frac{\overline{d}^{K}(a)}{d(a)}\overline{R}^{K}(A, B) ≤ C\overline{R}^{K}(A, B).

where the last inequality follows from that the graph is locally finite.

Proof of Theorem 1.1. One direction of the statement follows applying Lemma 2.1 to G and G′ then Lemma 2.2 to G′. For the given rough isometry Ψ we obtain

R(A, B) ≥ cR′ (Ψ(A), Ψ(B)) .

The opposite direction can be seen as follows. One can see that for two sets A, B and given Ψ with constants λ, and K an ”inverse” rough isometry Φ can be constructed, ( if d(A, B) > L ) with constants λ, 3K satisfying

Φ ∘ Ψ(A) ⊂ A

and

Φ ∘ Ψ(B) ⊂ B.

The trick of the construction is easy. Simply one should select an y ∈ A ∩ Ψ^{−1}(z) if A ∩ Ψ^{−1}(z) ≠ ∅ (or for B respectively) and set Φ (z) = y. This construction and the resistance estimates need that the files and their images are disjoint which holds if L ≥ \frac{1}{λ^{2}} (2λK + 6K). Having this Φ we apply the above estimate again to receive

R′ [Ψ(A), Ψ(A)] ≥ c′′R [Φ ∘ Ψ(A), Φ ∘ Ψ(B)] ≥ c′′R (A, B)

which gives the desired comparison.

3 Acknowledgment

The author is indebted to G. Elek turning his interest to the problem of rough isometry and also for the inspiring discussions. Thanks are also due to the referee for the valuable comments and remarks.

4 Bibliography

References

[B] Benjamini, I., Instability of the Liouville property for quasi-isometric graphs and manifolds of polynomial volume growth, J. Theor. Prob., 4., (1991) 631-637

[BS] Benjamini, I., Schramm, O. Harmonic functions on planar and almost planar graphs and manifolds, via circle packings, Invent. Math. 126 (1996), 565-587

[DS] Doyle, P.G., Snell, J. L., Random walks and electric networks, The Carus Mathematical Monographs, 22, (1884)

[GT] Grigory’an A., Telcs, A. Sub-Gaussian estimates of the heat kernels on infinite graphs, to appear in Duke Math. J.

[H] Holopainen, I. A sharp L^{q}-Liouville theorem for p-harmonic functions. Israel J. Math. 115 (2000), 363–379.

[HS] Holopainen, I., Soardi, P.M., A strong Liouville theorem for p-harmonic functions on graphs, Ann. Acad. Sci. Fenn. Ser. A I Math. 22 (1997), 205–226,

[K] Kanai, M., Rough isometries and parabolicity of Riemannian manifolds, J. Math. Soc. Japan, 38,227-238, (1986)

[L] Lyons, T., Instability of the Liouville property for quasi-isometric Riemannian manifolds and reversible Markov chains, J. Differential Geom., 26, (1987), 33-66

[PS] Pittet, Ch., Saloff-Coste, L., A survey on the relationship between volume growth, isoperimetry, and the behavior of simple random walk on Cayley graphs, with examples, preprint

[T1] Telcs, A., Random walks on graphs, electric networks and fractals, Prob. Theo. and Rel. Fields, 82, (1989), 435-449

[T2] Telcs, A., Volume and time doubling of graphs and random walks, the strongly recurrent case to appear in Comm. Pure and Appl. Math.

[W] Woess W., ”Random Walks on Infinite Graphs and Groups”, Cambridge Tracts in Mathematics 138, Cambridge University Press, 334+xi pages, 2000.