On the norms of the random walks on planar graphs
Żuk, Andrzej
Annales de l'Institut Fourier, Tome 47 (1997), p. 1463-1490 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

On considère la marche aléatoire simple sur les graphes planaires. Pour certaines familles de ces graphes, on donne des bornes supérieures explicites de la norme de l’opérateur de marche aléatoire en terme du nombre minimal des arêtes à chaque sommet. On démontre que pour un grand nombre de graphes planaires le rayon spectral de cette marche aléatoire est plus petit que un.

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.

@article{AIF_1997__47_5_1463_0,
     author = {\.Zuk, Andrzej},
     title = {On the norms of the random walks on planar graphs},
     journal = {Annales de l'Institut Fourier},
     volume = {47},
     year = {1997},
     pages = {1463-1490},
     doi = {10.5802/aif.1606},
     mrnumber = {99g:60127},
     zbl = {0897.60079},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_1997__47_5_1463_0}
}

Żuk, Andrzej. On the norms of the random walks on planar graphs. Annales de l'Institut Fourier, Tome 47 (1997) pp. 1463-1490. doi : 10.5802/aif.1606. http://gdmltest.u-ga.fr/item/AIF_1997__47_5_1463_0/

[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. | MR 973878 | Zbl 0677.31006

[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. | MR 98d:60133a | Zbl 0872.60051

[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. | MR 53 #6645 | Zbl 0212.44903

[4] P.A. Cherix, A. Valette, On spectra of simple random walks on one-relator groups, Pacific J. Math. (to appear). | Zbl 0865.60059

[5] Y. Colin De Verdière, Spectres de graphes, cours de DEA, Grenoble, 1995.

[6] J. Dodziuk, Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks, Trans. Amer. Math. Soc., 284, n° 2 (1984), 787-794. | Zbl 0512.39001

[7] V. Kaimanovich, Dirichlet norms, capacities and generalized isoperimetric inequalities for Markov operators, Analysis, 1 (1992), 61-82. | Zbl 05009152

[8] H. Kesten, Symmetric random walks on groups, Trans. Amer. Math. Soc., 92 (1959), 336-354. | MR 22 #253 | Zbl 0092.33503

[9] P. Papasoglu, Strongly geodesically automatic groups are hyperbolic, Invent. Math., 121 (1995), 323-334. | MR 96h:20073 | Zbl 0834.20040

[10] P.M. Soardi, Recurrence and transience of the edge graph of a tiling of the Euclidean plane, Math. Ann., 287 (1990), 613-626. | MR 92b:52044 | Zbl 0679.60072

[11] R.S. Strichartz, Analysis of the Laplacian on the Complete Riemannian Manifold, Journal of Functional Analysis, 52 (1983), 48-79. | MR 84m:58138 | Zbl 0515.58037

[12] W. Woess, Random walks on infinite graphs and groups — a survey of selected topics, Bull. London Math. Soc., 26 (1994), 1-60. | MR 94i:60081 | Zbl 0830.60061

[13] W. Woess, A note on tilings and strong isoperimetric inequality, preprint, 1996.

[14] A. Żuk, A remark on the norms of a random walk on surface groups, Coll. Math., 72, n° 1 (1997), 195-206. | MR 98d:60133b | Zbl 0872.60052

[15] A. Żuk, A generalized Følner condition and the norms of random walks operators on groups, preprint, 1996. | Zbl 0990.43001