Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-02-06T20:21:52.411Z Has data issue: false hasContentIssue false
  • English
  • Français

A Numerical Lower Bound for the Spectral Radius of Random Walks on Surface Groups

Part of: Probability theory on algebraic and topological structures Graph theory Special aspects of infinite or finite groups

Published online by Cambridge University Press:  29 January 2015

S. GOUEZEL
S. GOUEZEL*
Affiliation:
IRMAR, CNRS UMR 6625, Université de Rennes 1, 35042 Rennes, France (e-mail: sebastien.gouezel@univ-rennes1.fr)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Estimating numerically the spectral radius of a random walk on a non-amenable graph is complicated, since the cardinality of balls grows exponentially fast with the radius. We propose an algorithm to get a bound from below for this spectral radius in Cayley graphs with finitely many cone types (including for instance hyperbolic groups). In the genus 2 surface group, it improves by an order of magnitude the previous best bound, due to Bartholdi.

MSC classification

Primary: 60B15: Probability measures on groups or semigroups, Fourier transforms, factorization
Secondary: 20F67: Hyperbolic groups and nonpositively curved groups 05C81: Random walks on graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Issue 6 , November 2015 , pp. 838 - 856
Copyright
Copyright © Cambridge University Press 2015 

References

[1] Bartholdi, L. (2004) Cactus trees and lower bounds on the spectral radius of vertex-transitive graphs. In Random Walks and Geometry, de Gruyter, pp. 349–361.Google Scholar
[2] Cannon, J. W. (1983) The growth of the closed surface groups and the compact hyperbolic Coxeter groups. Preprint.Google Scholar
[3] Elder, M., Rechnitzer, A. and Wong, T. (2012) On the cogrowth of Thompson's group F . Groups Complex. Cryptol. 4 301–320.Google Scholar
[4] Floyd, W. J. and Plotnick, S. P. (1987) Growth functions on Fuchsian groups and the Euler characteristic. Inventio Math. 88 1–29.Google Scholar
[5] Gouëzel, S. and Lalley, S. P. (2013) Random walks on co-compact Fuchsian groups. Ann. Sci. Éc. Norm. Supér. (4) 46 129–173.Google Scholar
[6] Kesten, H. (1959) Symmetric random walks on groups. Trans. Amer. Math. Soc. 92 336–354.Google Scholar
[7] Nagnibeda, T. (1997) An upper bound for the spectral radius of a random walk on surface groups. Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 240 154–165, 293–294.Google Scholar
[8] Nagnibeda, T. (2004) Random walks, spectral radii, and Ramanujan graphs. In Random Walks and Geometry, de Gruyter, pp. 487–500.Google Scholar
[9] Nagnibeda, T. and Woess, W. (2002) Random walks on trees with finitely many cone types. J. Theoret. Probab. 15 383–422.Google Scholar
[10] Woess, W. (2000) Random Walks on Infinite Graphs and Groups, Vol. 138 of Cambridge Tracts in Mathematics, Cambridge University Press.Google Scholar