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
[Aspects asymptotiques des graphes de Schreier et groupes des Tours de Hanoï]

Présenté par : É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.

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 :

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/

Bibliographie
Cité par

[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

Sagar Saha; K. V. Krishna A branch group in a class of non-contracting weakly regular branch groups, International Journal of Algebra and Computation, Volume 34 (2024) no. 6, pp. 901-918 | DOI:10.1142/s021819672450036x | Zbl:7939704
Zoran Šunić; Jone Uria-Albizuri Portrait growth in contracting, regular branch groups, Journal of Algebra and its Applications, Volume 22 (2023) no. 8, p. 18 (Id/No 2350180) | DOI:10.1142/s0219498823501803 | Zbl:1520.20056
Rostislav Grigorchuk; Dmytro Savchuk Solenoidal maps, automatic sequences, van der Put series, and Mealy automata, Journal of the Australian Mathematical Society, Volume 114 (2023) no. 1, pp. 78-109 | DOI:10.1017/s1446788722000027 | Zbl:1521.68080
Mario Szegedy; Jingjin Yu Rubik Tables and object rearrangement, The International Journal of Robotics Research, Volume 42 (2023) no. 6, p. 459 | DOI:10.1177/02783649211059844
Adrien Le Boudec; Nicolás Matte Bon A commutator lemma for confined subgroups and applications to groups acting on rooted trees, Transactions of the American Mathematical Society, Volume 376 (2023) no. 10, pp. 7187-7233 | DOI:10.1090/tran/8965 | Zbl:1526.20039
Laurent Bartholdi; Michael Figelius; Markus Lohrey; Armin Weiß Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems, ACM Transactions on Computation Theory, Volume 14 (2022) no. 3-4, p. 41 (Id/No 11) | DOI:10.1145/3569708 | Zbl:7988316
Laurent Bartholdi Monadic second-order logic and the domino problem on self-similar graphs, Groups, Geometry, and Dynamics, Volume 16 (2022) no. 4, pp. 1423-1459 | DOI:10.4171/ggd/689 | Zbl:7672034
Laurent Bartholdi Book review of: F. Bassino et al., Complexity and randomness in group theory. GAGTA book 1, Jahresbericht der Deutschen Mathematiker-Vereinigung (DMV), Volume 124 (2022) no. 2, pp. 129-135 | DOI:10.1365/s13291-022-00248-6 | Zbl:1522.00015
M. Cavaleri; D. D'Angeli; A. Donno; E. Rodaro Graph automaton groups, Advances in Group Theory and Applications, Volume 11 (2021), pp. 75-112 | Zbl:1495.20038
Mario Szegedy; Jingjin Yu On rearrangement of items stored in stacks, Algorithmic foundations of robotics XIV. Proceedings of the fourteenth workshop on the algorithmic foundations of robotics, Cham: Springer, 2021, pp. 518-533 | DOI:10.1007/978-3-030-66723-8_31 | Zbl:1469.68137
Rostislav Grigorchuk; Supun Samarakoon Integrable and Chaotic Systems Associated with Fractal Groups, Entropy, Volume 23 (2021) no. 2, p. 237 | DOI:10.3390/e23020237
Laurent Bartholdi; Michael Figelius; Markus Lohrey; Armin Weiß Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems, 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings, Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik, 2020, p. 29 (Id/No 29) | DOI:10.4230/lipics.ccc.2020.29 | Zbl:7561757
Rachel Skipper The congruence subgroup problem for a family of branch groups, International Journal of Algebra and Computation, Volume 30 (2020) no. 2, pp. 397-418 | DOI:10.1142/s0218196720500046 | Zbl:1452.20023
Daniele D'Angeli; Thibault Godin; Ines Klimann; Matthieu Picantin; Emanuele Rodaro Boundary dynamics for bireversible and for contracting automaton groups, International Journal of Algebra and Computation, Volume 30 (2020) no. 2, pp. 431-449 | DOI:10.1142/s021819672050006x | Zbl:1486.20031
Elsayed Ahmed; Dmytro Savchuk Endomorphisms of regular rooted trees induced by the action of polynomials on the ring $Z_{d}$ of $d$ -adic integers, Journal of Algebra and its Applications, Volume 19 (2020) no. 8, p. 20 (Id/No 2050154) | DOI:10.1142/s0219498820501546 | Zbl:1496.20047
Zhizhuo Zhang; Bo Wu Spectral analysis and consensus problems for a class of fractal network models, Physica Scripta, Volume 95 (2020) no. 8, p. 085210 | DOI:10.1088/1402-4896/ab9e96
Alejandra Garrido; Jone Uria-Albizuri Pro- $C$ congruence properties for groups of rooted tree automorphisms, Archiv der Mathematik, Volume 112 (2019) no. 2, pp. 123-137 | DOI:10.1007/s00013-018-1278-6 | Zbl:1428.20029
Rostislav Grigorchuk; Dima Grigoriev Key agreement based on automaton groups, Groups, Complexity, Cryptology, Volume 11 (2019) no. 2, pp. 77-81 | DOI:10.1515/gcc-2019-2012 | Zbl:1435.20043
Rachel Skipper A constructive proof that the Hanoi towers group has non-trivial rigid kernel, Topology Proceedings, Volume 53 (2019), pp. 1-14 | Zbl:1479.20020
Rostislav Grigorchuk; Daniel Lenz; Tatiana Nagnibeda Spectra of Schreier graphs of Grigorchuk's group and Schroedinger operators with aperiodic order, Mathematische Annalen, Volume 370 (2018) no. 3-4, pp. 1607-1637 | DOI:10.1007/s00208-017-1573-8 | Zbl:1383.05196
Andreas M. Hinz; Sandi Klavžar; Sara Sabrina Zemljič A survey and classification of Sierpiński-type graphs, Discrete Applied Mathematics, Volume 217 (2017), pp. 565-600 | DOI:10.1016/j.dam.2016.09.024 | Zbl:1358.05219
Rostislav Grigorchuk; Daniel Lenz; Tatiana Nagnibeda Schreier Graphs of Grigorchuk's Group and a Subshift Associated to a Nonprimitive Substitution, Groups, Graphs and Random Walks (2017), p. 250 | DOI:10.1017/9781316576571.012
Joe P. Chen; Luke G. Rogers; Loren Anderson; Ulysses Andrews; Antoni Brzoska; Aubrey Coffey; Hannah Davis; Lee Fisher; Madeline Hansalik; Stephen Loew; Alexander Teplyaev Power dissipation in fractal AC circuits, Journal of Physics A: Mathematical and Theoretical, Volume 50 (2017) no. 32, p. 20 (Id/No 325205) | DOI:10.1088/1751-8121/aa7a66 | Zbl:1375.78030
Gideon Amir; Omer Angel; Nicolás Matte Bon; Bálint Virág The Liouville property for groups acting on rooted trees, Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, Volume 52 (2016) no. 4 | DOI:10.1214/15-aihp697
Rostislav Grigorchuk; Volodymyr Nekrashevych; Zoran Šunić From self-similar groups to self-similar sets and spectra, Fractal geometry and stochastics V. Selected papers of the 5th conference, Tabarz, Germany, March 24–29, 2014, Cham: Springer, 2015, pp. 175-207 | DOI:10.1007/978-3-319-18660-3_11 | Zbl:1359.37008
Dmytro Savchuk Schreier graphs of actions of Thompson's group $F$ on the unit interval and on the Cantor set, Geometriae Dedicata, Volume 175 (2015), pp. 355-372 | DOI:10.1007/s10711-014-9951-9 | Zbl:1309.05094
Mustafa Gökhan Benli; Rostislav Grigorchuk; Pierre de la Harpe Amenable groups without finitely presented amenable covers, Bulletin of Mathematical Sciences, Volume 3 (2013) no. 1, pp. 73-131 | DOI:10.1007/s13373-013-0031-5 | Zbl:1352.20025
Ievgen Bondarenko; Tullio Ceccherini-Silberstein; Alfredo Donno; Volodymyr Nekrashevych On a family of Schreier graphs of intermediate growth associated with a self-similar group, European Journal of Combinatorics, Volume 33 (2012) no. 7, pp. 1408-1421 | DOI:10.1016/j.ejc.2012.03.006 | Zbl:1245.05060
Rostislav I. Grigorchuk; Piotr W. Nowak Diameters, distortion, and eigenvalues, European Journal of Combinatorics, Volume 33 (2012) no. 7, pp. 1574-1587 | DOI:10.1016/j.ejc.2012.03.019 | Zbl:1246.05046
Zoran Šunić Twin towers of Hanoi, European Journal of Combinatorics, Volume 33 (2012) no. 7, pp. 1691-1707 | DOI:10.1016/j.ejc.2012.03.026 | Zbl:1254.90287
Daniel J. Kelleher; Benjamin A. Steinhurst; Chuen-Ming M. Wong From self-similar structures to self-similar groups., International Journal of Algebra and Computation, Volume 22 (2012) no. 7, p. 16 (Id/No 1250056) | DOI:10.1142/s0218196712500567 | Zbl:1287.20037
Laurent Bartholdi; Olivier Siegenthaler; Pavel Zalesskii The congruence subgroup problem for branch groups., Israel Journal of Mathematics, Volume 187 (2012), pp. 419-450 | DOI:10.1007/s11856-011-0086-5 | Zbl:1271.20031
Ievgen V. Bondarenko Growth of Schreier graphs of automaton groups., Mathematische Annalen, Volume 354 (2012) no. 2, pp. 765-785 | DOI:10.1007/s00208-011-0757-x | Zbl:1280.20042
Zoran Šunić Finite self-similar $p$ -groups with Abelian first level stabilizers., International Journal of Algebra and Computation, Volume 21 (2011) no. 1-2, pp. 355-364 | DOI:10.1142/s0218196711006200 | Zbl:1233.20019
Shotaro Makisumi; Grace Stadnyk; Benjamin Steinhurst Modified Hanoi towers groups and limit spaces., International Journal of Algebra and Computation, Volume 21 (2011) no. 6, pp. 867-887 | DOI:10.1142/s0218196711006443 | Zbl:1258.20021
René Hartung Coset enumeration for certain infinitely presented groups., International Journal of Algebra and Computation, Volume 21 (2011) no. 8, pp. 1369-1380 | DOI:10.1142/s0218196711006637 | Zbl:1235.20031
Elmar Teufl; Stephan Wagner Resistance scaling and the number of spanning trees in self-similar lattices, Journal of Statistical Physics, Volume 142 (2011) no. 4, pp. 879-897 | DOI:10.1007/s10955-011-0140-z | Zbl:1213.82024
R. I. Grigorchuk Some topics in the dynamics of group actions on rooted trees., Proceedings of the Steklov Institute of Mathematics, Volume 273 (2011), pp. 64-175 | DOI:10.1134/s0081543811040067 | Zbl:1268.20027
Shunqi Wu; Zhongzhi Zhang; Guanrong Chen Random walks on dual Sierpinski gaskets, The European Physical Journal B. Condensed Matter and Complex Systems, Volume 82 (2011) no. 1, pp. 91-96 | DOI:10.1140/epjb/e2011-20338-0 | Zbl:1515.82075
Elmar Teufl; Stephan Wagner Enumeration of matchings in families of self-similar graphs, Discrete Applied Mathematics, Volume 158 (2010) no. 14, pp. 1524-1535 | DOI:10.1016/j.dam.2010.05.006 | Zbl:1215.05087
So Eun Park The Group of Symmetries of the Tower of Hanoi Graph, The American Mathematical Monthly, Volume 117 (2010) no. 4, p. 353 | DOI:10.4169/000298910x480829
J.-F. Quint Harmonic analysis on the Pascal graph, Journal of Functional Analysis, Volume 256 (2009) no. 10, pp. 3409-3460 | DOI:10.1016/j.jfa.2009.01.011 | Zbl:1168.47039
N. Bajorin; T. Chen; A. Dagan; C. Emmons; M. Hussein; M. Khalil; P. Mody; B. Steinhurst; A. Teplyaev Vibration spectra of finitely ramifield, symmetric fractals, Fractals, Volume 16 (2008) no. 3, pp. 243-258 | DOI:10.1142/s0218348x08004010 | Zbl:1160.28302
Thomas Delzant; Rostislav Grigorchuk Homomorphic Images of Branch Groups, and Serre’s Property (FA), Geometry and Dynamics of Groups and Spaces, Volume 265 (2008), p. 353 | DOI:10.1007/978-3-7643-8608-5_7
N Bajorin; T Chen; A Dagan; C Emmons; M Hussein; M Khalil; P Mody; B Steinhurst; A Teplyaev Vibration modes of 3n-gaskets and other fractals, Journal of Physics A: Mathematical and Theoretical, Volume 41 (2008) no. 1, p. 015101 | DOI:10.1088/1751-8113/41/1/015101
Zoran Šunić Hausdorff dimension in a family of self-similar groups., Geometriae Dedicata, Volume 124 (2007), pp. 213-236 | DOI:10.1007/s10711-006-9106-8 | Zbl:1169.20015

Cité par 46 documents. Sources : Crossref, zbMATH

Commentaires - Politique

Il n'y a aucun commentaire pour cet article. Soyez le premier à écrire un commentaire !

Publier un nouveau commentaire:

Publier une nouvelle réponse: