On the norms of the random walks on planar graphs

Andrzej Żuk

Annales de l'institut Fourier (1997)

  • Volume: 47, Issue: 5, page 1463-1490
  • ISSN: 0373-0956

Abstract

top
We consider the nearest neighbor random walk on planar graphs. For certain families of these graphs, we give explicit upper bounds on the norm of the random walk operator in terms of the minimal number of edges at each vertex. We show that for a wide range of planar graphs the spectral radius of the random walk is less than one.

How to cite

top

Żuk, Andrzej. "On the norms of the random walks on planar graphs." Annales de l'institut Fourier 47.5 (1997): 1463-1490. <http://eudml.org/doc/75270>.

@article{Żuk1997,
abstract = {We consider the nearest neighbor random walk on planar graphs. For certain families of these graphs, we give explicit upper bounds on the norm of the random walk operator in terms of the minimal number of edges at each vertex. We show that for a wide range of planar graphs the spectral radius of the random walk is less than one.},
author = {Żuk, Andrzej},
journal = {Annales de l'institut Fourier},
keywords = {random walks; norm of the operator; planar graphs; upper bounds},
language = {eng},
number = {5},
pages = {1463-1490},
publisher = {Association des Annales de l'Institut Fourier},
title = {On the norms of the random walks on planar graphs},
url = {http://eudml.org/doc/75270},
volume = {47},
year = {1997},
}

TY - JOUR
AU - Żuk, Andrzej
TI - On the norms of the random walks on planar graphs
JO - Annales de l'institut Fourier
PY - 1997
PB - Association des Annales de l'Institut Fourier
VL - 47
IS - 5
SP - 1463
EP - 1490
AB - We consider the nearest neighbor random walk on planar graphs. For certain families of these graphs, we give explicit upper bounds on the norm of the random walk operator in terms of the minimal number of edges at each vertex. We show that for a wide range of planar graphs the spectral radius of the random walk is less than one.
LA - eng
KW - random walks; norm of the operator; planar graphs; upper bounds
UR - http://eudml.org/doc/75270
ER -

References

top
  1. [1] A. ANCONA, Positive harmonic functions and hyperbolicity. Potential theory, surveys and problems, Lecture Notes in Math., 1344, ed. J. Král et al., Springer, Berlin, 1988, 1-23. Zbl0677.31006MR973878
  2. [2] L. BARTHOLDI, S. CANTAT, T. CECCHERINI SILBERSTEIN, P. DE LA HARPE, Estimates for simple random walks on fundamental groups of surfaces, Coll. Math., 72, n° 1 (1997), 173-193. Zbl0872.60051MR98d:60133a
  3. [3] J. CHEEGER, A lower bound for the smallest eigenvalue of the Laplacian, in Problems in Analysis, Ganning (ed.) Princeton Univ. Press., 1970, 195-199. Zbl0212.44903MR53 #6645
  4. [4] P.A. CHERIX, A. VALETTE, On spectra of simple random walks on one-relator groups, Pacific J. Math. (to appear). Zbl0865.60059
  5. [5] Y. COLIN DE VERDIÈRE, Spectres de graphes, cours de DEA, Grenoble, 1995. 
  6. [6] J. DODZIUK, Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks, Trans. Amer. Math. Soc., 284, n° 2 (1984), 787-794. Zbl0512.39001
  7. [7] V. KAIMANOVICH, Dirichlet norms, capacities and generalized isoperimetric inequalities for Markov operators, Analysis, 1 (1992), 61-82. Zbl1081.31502
  8. [8] H. KESTEN, Symmetric random walks on groups, Trans. Amer. Math. Soc., 92 (1959), 336-354. Zbl0092.33503MR22 #253
  9. [9] P. PAPASOGLU, Strongly geodesically automatic groups are hyperbolic, Invent. Math., 121 (1995), 323-334. Zbl0834.20040MR96h:20073
  10. [10] P.M. SOARDI, Recurrence and transience of the edge graph of a tiling of the Euclidean plane, Math. Ann., 287 (1990), 613-626. Zbl0679.60072MR92b:52044
  11. [11] R.S. STRICHARTZ, Analysis of the Laplacian on the Complete Riemannian Manifold, Journal of Functional Analysis, 52 (1983), 48-79. Zbl0515.58037MR84m:58138
  12. [12] W. WOESS, Random walks on infinite graphs and groups — a survey of selected topics, Bull. London Math. Soc., 26 (1994), 1-60. Zbl0830.60061MR94i:60081
  13. [13] W. WOESS, A note on tilings and strong isoperimetric inequality, preprint, 1996. 
  14. [14] A. ŻUK, A remark on the norms of a random walk on surface groups, Coll. Math., 72, n° 1 (1997), 195-206. Zbl0872.60052MR98d:60133b
  15. [15] A. ŻUK, A generalized Følner condition and the norms of random walks operators on groups, preprint, 1996. Zbl0990.43001

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.