Asymptotic aspects of Schreier graphs and Hanoi Towers groups

Grigorchuk, Rostislav; Šunik´, Zoran

doi:10.1016/j.crma.2006.02.001

Group Theory

Asymptotic aspects of Schreier graphs and Hanoi Towers groups
[Aspects asymptotiques des graphes de Schreier et groupes des Tours de Hanoï]

Présenté par : Étienne Ghys

Grigorchuk, Rostislav ¹ ; Šunik´, Zoran ¹

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

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

Résumé
Abstract

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.

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.

Accepté le : 2006-01-30
Publié le : 2006-03-23

DOI : 10.1016/j.crma.2006.02.001

Affiliations des auteurs :

Grigorchuk, Rostislav ¹ ; Šunik´, Zoran ¹

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

@article{CRMATH_2006__342_8_545_0,
     author = {Grigorchuk, Rostislav and \v{S}unik{\textasciiacute}, Zoran},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2006.02.001/}
}

TY  - JOUR
AU  - Grigorchuk, Rostislav
AU  - Šunik´, Zoran
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2006.02.001/
DO  - 10.1016/j.crma.2006.02.001
LA  - en
ID  - CRMATH_2006__342_8_545_0
ER  -

%0 Journal Article
%A Grigorchuk, Rostislav
%A Šunik´, Zoran
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2006.02.001/
%R 10.1016/j.crma.2006.02.001
%G en
%F CRMATH_2006__342_8_545_0

Grigorchuk, Rostislav; Šunik´, Zoran. Asymptotic aspects of Schreier graphs and Hanoi Towers groups. Comptes Rendus. Mathématique, Tome 342 (2006) no. 8, pp. 545-550. doi : 10.1016/j.crma.2006.02.001. http://www.numdam.org/articles/10.1016/j.crma.2006.02.001/

Bibliographie
Cité par

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

[2] Bartholdi, L.; Grigorchuk, R.I. 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] Bartholdi, L.; Grigorchuk, R.I.; Šunik´, Z. Branch groups, Handbook of Algebra, vol. 3, North-Holland, Amsterdam, 2003, pp. 989-1112

[4] Bartholdi, L.; Šunik´, Z. 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] Benjamini, I.; Hoffman, C. ω-periodic graphs, Electron. J. Combin., Volume 12 (2005) no. 1, p. R46 (electronic, 12 p)

[6] Bode, J.-P.; Hinz, A.M. 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] Erschler, A. Boundary behavior for groups of subexponential growth, Ann. of Math. (2), Volume 160 (2004) no. 3, pp. 1183-1210

[9] Grabner, P.J.; Woess, W. 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] Grigorchuk, R.I. On Burnside's problem on periodic groups, Funktsional. Anal. i Prilozhen., Volume 14 (1980) no. 1, pp. 53-54

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

[12] Grigorchuk, R.; Żuk, A. 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] Grigorchuk, R.I.; Żuk, A. 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] Klavžar, S.; Milutinović, U.; Petr, C. 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] Nekrashevych, V. Self-Similar Groups, Math. Surveys Monogr., vol. 117, American Mathematical Society, Providence, RI, 2005

[16] Szegedy, M. 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] Teplyaev, A. Spectral analysis on infinite Sierpiński gaskets, J. Funct. Anal., Volume 159 (1998) no. 2, pp. 537-567

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

Cité par Sources :