4
$\begingroup$

Let's say two locally finite, connected, undirected, infinite graphs are "finite perturbations" of each other if one can remove a finite subset from each and obtain isomorphic graphs (which are now possibly disconnected).

My question is: Is there any literature on properties which are stable under this type of perturbation?

For example, does anyone know of a reference for the following statements:

  1. If a graph admits a non-constant bounded harmonic function then so does every finite perturbation of it.
  2. If the simple random walk on a graph is recurrent then so is the simple random walk on any finite perturbation.
  3. If the simple random walk on a graph has positive speed with positive probability, then the same holds for every finite perturbation of it.
  4. If the simple random walk on a graph has positive speed almost surely, then the same holds for every finite perturbation of it.
$\endgroup$

2 Answers 2

1
$\begingroup$

The references for these can be found in Doyle and Snell's deathless classic (which is available for free on arXiv.org. ). Section 2.4 is particularly a propos.

Doyle, Peter G.; Snell, J.Laurie, Random walks and electric networks, The Carus Mathematical Monographs, 22. Washington, D. C.: The Mathematical Association of America. Distr. by John Wiley & Sons, New York etc. XIII, 159 p. £ 22.00 (1984). ZBL0583.60065.

$\endgroup$
1
$\begingroup$

The answers to all these questions are "yes" and are more or less obvious from the definitions of the corresponding properties. This is the reason why they don't appear in the literature in an explicit form. The key is property (2) - which is actually much more robust and is preserved under rough isometries (Kanai). However, the latter is not the case for the other properties.

$\endgroup$
1
  • $\begingroup$ This question is a reference request. I'm well aware of Kanai's result. I think the notion of finite perturbation is quite natural and was hoping there might be a systematic treatment of it somewhere. Also, there are many other questions one might ask besides the short list above (all of which, I agree, are quite elementary). For example, one might ask about the spectral gap of the Laplacian, or more generally its spectral measure. $\endgroup$ Jan 5, 2017 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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