Asymptotic aspects of Schreier graphs and Hanoi Towers groups

Rostislav Grigorchuk; Zoran Šunik´

doi:10.1016/j.crma.2006.02.001

Group Theory

Asymptotic aspects of Schreier graphs and Hanoi Towers groups

Presented by: Étienne Ghys

Rostislav Grigorchuk ¹; Zoran Šunik´¹

¹ Department of Mathematics, Texas A&M University, MS-3368, College Station, TX, 77843-3368, USA

Comptes Rendus. Mathématique, Volume 342 (2006) no. 8, pp. 545-550.

Abstract
Résumé

We present relations between growth, growth of diameters and the rate of vanishing of the spectral gap in Schreier graphs of automaton groups. In particular, we introduce a series of examples, called Hanoi Towers groups since they model the well known Hanoi Towers Problem, that illustrate some of the possible types of behavior.

On montre quelques relations entre la croissance, la croissance des diamètres et la vitesse avec laquelle le trou spectral dans les graphes de Schreier des groupes automatiques tend vers zéro. En particulier, on introduit un certain nombre d'exemples, les groupes dits des Tours de Hanoï car ils donnent un modèle du célèbre problème des Tours de Hanoï, et qui illustrent des types possibles de comportement.

Accepted: 2006-01-30
Published online: 2006-03-23

DOI: 10.1016/j.crma.2006.02.001

Author's affiliations:

Rostislav Grigorchuk ¹; Zoran Šunik´ ¹

¹ Department of Mathematics, Texas A&M University, MS-3368, College Station, TX, 77843-3368, USA

@article{CRMATH_2006__342_8_545_0,
     author = {Rostislav Grigorchuk and Zoran \v{S}unik{\textasciiacute}},
     title = {Asymptotic aspects of {Schreier} graphs and {Hanoi} {Towers} groups},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {545--550},
     publisher = {Elsevier},
     volume = {342},
     number = {8},
     year = {2006},
     doi = {10.1016/j.crma.2006.02.001},
     language = {en},
}

TY  - JOUR
AU  - Rostislav Grigorchuk
AU  - Zoran Šunik´
TI  - Asymptotic aspects of Schreier graphs and Hanoi Towers groups
JO  - Comptes Rendus. Mathématique
PY  - 2006
SP  - 545
EP  - 550
VL  - 342
IS  - 8
PB  - Elsevier
DO  - 10.1016/j.crma.2006.02.001
LA  - en
ID  - CRMATH_2006__342_8_545_0
ER  -

%0 Journal Article
%A Rostislav Grigorchuk
%A Zoran Šunik´
%T Asymptotic aspects of Schreier graphs and Hanoi Towers groups
%J Comptes Rendus. Mathématique
%D 2006
%P 545-550
%V 342
%N 8
%I Elsevier
%R 10.1016/j.crma.2006.02.001
%G en
%F CRMATH_2006__342_8_545_0

Rostislav Grigorchuk; Zoran Šunik´. Asymptotic aspects of Schreier graphs and Hanoi Towers groups. Comptes Rendus. Mathématique, Volume 342 (2006) no. 8, pp. 545-550. doi : 10.1016/j.crma.2006.02.001. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2006.02.001/

References
Cited by

[1] S.V. Aleshin A free group of finite automata, Vestnik Moskov. Univ. Ser. I Mat. Mekh. (4) (1983), pp. 12-14

[2] L. Bartholdi; R.I. Grigorchuk On the spectrum of Hecke type operators related to some fractal groups, Tr. Mat. Inst. Steklova, Volume 231 (2000), pp. 5-45 (Din. Sist., Avtom. i Beskon. Gruppy)

[3] L. Bartholdi; R.I. Grigorchuk; Z. Šunik´ Branch groups, Handbook of Algebra, vol. 3, North-Holland, Amsterdam, 2003, pp. 989-1112

[4] L. Bartholdi; Z. Šunik´ Some solvable automaton groups, Topological and Asymptotic Aspects of Group Theory, Contemp. Math., vol. 394, Amer. Math. Soc., Providence, RI, 2006, pp. 11-30

[5] I. Benjamini; C. Hoffman ω-periodic graphs, Electron. J. Combin., Volume 12 (2005) no. 1, p. R46 (electronic, 12 p)

[6] J.-P. Bode; A.M. Hinz Results and open problems on the Tower of Hanoi, Congr. Numer., Volume 139 (1999), pp. 113-122

[7] I. Bondarenko, T. Ceccherini-Silberstein, V. Nekrashevych, Amenable graphs with dense holonomy and no cocompact isometry groups, preprint, 2006

[8] A. Erschler Boundary behavior for groups of subexponential growth, Ann. of Math. (2), Volume 160 (2004) no. 3, pp. 1183-1210

[9] P.J. Grabner; W. Woess Functional iterations and periodic oscillations for simple random walk on the Sierpiński graph, Stochastic Process. Appl., Volume 69 (1997) no. 1, pp. 127-138

[10] R.I. Grigorchuk On Burnside's problem on periodic groups, Funktsional. Anal. i Prilozhen., Volume 14 (1980) no. 1, pp. 53-54

[11] R.I. Grigorchuk; V.V. Nekrashevich; V.I. Sushchanskiĭ Automata, dynamical systems, and groups, Tr. Mat. Inst. Steklova, Volume 231 (2000), pp. 134-214 (Din. Sist., Avtom. i Beskon. Gruppy)

[12] R. Grigorchuk; A. Żuk On the asymptotic spectrum of random walks on infinite families of graphs, Random Walks and Discrete Potential Theory, Sympos. Math., vol. XXXIX, Cambridge Univ. Press, Cambridge, 1999, pp. 188-204

[13] R.I. Grigorchuk; A. Żuk The lamplighter group as a group generated by a 2-state automaton, and its spectrum, Geom. Dedicata, Volume 87 (2001) no. 1–3, pp. 209-244

[14] S. Klavžar; U. Milutinović; C. Petr On the Frame–Stewart algorithm for the multi-peg Tower of Hanoi problem, Discrete Appl. Math., Volume 120 (2002) no. 1–3, pp. 141-157

[15] V. Nekrashevych Self-Similar Groups, Math. Surveys Monogr., vol. 117, American Mathematical Society, Providence, RI, 2005

[16] M. Szegedy In how many steps the k peg version of the Towers of Hanoi game can be solved?, STACS 99, Trier (Lecture Notes in Comput. Sci.), Volume vol. 1563, Springer, Berlin (1999), pp. 356-361

[17] A. Teplyaev Spectral analysis on infinite Sierpiński gaskets, J. Funct. Anal., Volume 159 (1998) no. 2, pp. 537-567

[18] M. Vorobets; Y. Vorobets On a free group of transformations defined by an automaton, 2006 | arXiv

Cited by Sources:

Comments - Policy