Some topics in the dynamics of group actions on rooted trees

R. I. Grigorchuk

Informatics and Automation, Modern problems of mathematics, Tome 273 (2011), pp. 72-191.

Résumé

This article combines the features of a survey and a research paper. It presents a review of some results obtained during the last decade in problems related to the dynamics of branch and self-similar groups on the boundary of a spherically homogeneous rooted tree and to the combinatorics and asymptotic properties of Schreier graphs associated with a group or with its action. Special emphasis is placed on the study of essentially free actions of self-similar groups, which are antipodes to branch actions. At the same time, the theme “free versus nonfree” runs through the paper. Sufficient conditions are obtained for the essential freeness of an action of a self-similar group on the boundary of a tree. Specific examples of such actions are given. Constructions of the associated dynamical system and the Schreier dynamical system generated by a Schreier graph are presented. For groups acting on trees, a trace on the associated $C^*$-algebra generated by a Koopman representation is introduced, and its role in the study of von Neumann factors, the spectral properties of groups, Schreier graphs, and elements of the associated $C^*$-algebra is demonstrated. The concepts of asymptotic expander and asymptotic Ramanujan graph are introduced, and examples of such graphs are given. Questions related to the notion of the cost of action and the notion of rank gradient are discussed.

Bibliographie

[1] Abért M., “Group laws and free subgroups in topological groups”, Bull. London Math. Soc., 37:4 (2005), 525–534 | DOI | MR | Zbl

[2] Abért M., Elek G., Non-abelian free groups admit non-essentially free actions on rooted trees, E-print, 2007, arXiv: 0707.0970 [math.GR]

[3] Abért M., Elek G., Dynamical properties of profinite actions, E-print, 2010, arXiv: 1005.3188 [math.GR] | Zbl

[4] Abért M., Jaikin-Zapirain A., Nikolov N., “The rank gradient from a combinatorial viewpoint”, Groups, Geom., and Dyn., 5:2 (2011), 213–230, arXiv: math/0701925 [math.GR] | DOI | MR | Zbl

[5] Abért M., Nikolov N., “Rank gradient, cost of groups and the rank versus Heegaard genus problem”, J. Eur. Math. Soc. (to appear) , arXiv: math/0701361 [math.GR]

[6] Abért M., Virág B., “Dimension and randomness in groups acting on rooted trees”, J. Amer. Math. Soc., 18:1 (2005), 157–192 | DOI | MR | Zbl

[7] Aleshin S.V., “Svobodnaya gruppa konechnykh avtomatov”, Vestn. Mosk. un-ta. Matematika. Mekhanika, 1983, no. 4, 12–14 | MR | Zbl

[8] Allums D.J., Grigorchuk R.I., The rank gradient and the lamplighter group, Preprint, 2011 http://www.math.tamu.edu/~grigorch/publications/lamplighter.pdf

[9] Amir G., Angel O., Virág B., Amenability of linear-activity automaton groups, E-print, 2009, arXiv: 0905.2007 [math.GR]

[10] Atiyah M.F., “Elliptic operators, discrete groups and von Neumann algebras”, Analyse et topologie, Colloque en l'honneur de Henri Cartan (Orsay, 1974), Astérisque, 32–33, Soc. math. France, Paris, 1976, 43–72 | MR

[11] Bacher R., de la Harpe P., Nagnibeda T., “The lattice of integral flows and the lattice of integral cuts on a finite graph”, Bull. Soc. math. France, 125:2 (1997), 167–198 | MR | Zbl

[12] Barlow M.T., “Diffusions on fractals”, Lectures on probability theory and statistics (Saint-Flour, 1995), Lect. Notes Math., 1690, Springer, Berlin, 1998, 1–121 | DOI | MR | Zbl

[13] Barnea Y., Ershov M., Weigel T., Abstract commensurators of profinite groups, E-print, 2008, arXiv: 0810.2060 [math.GR] | MR

[14] Bartholdi L., “Endomorphic presentations of branch groups”, J. Algebra, 268:2 (2003), 419–443 | DOI | MR | Zbl

[15] Bartholdi L., Erschler A.G., Growth of permutational extensions, E-print, 2010, arXiv: 1011.5266 [math.GR]

[16] Bartholdi L., Grigorchuk R.I., “On the spectrum of Hecke type operators related to some fractal groups”, Tr. MIAN, 231, 2000, 5–45 | MR | Zbl

[17] Bartholdi L., Grigorchuk R.I., “On parabolic subgroups and Hecke algebras of some fractal groups”, Serdica Math. J., 28:1 (2002), 47–90 | MR | Zbl

[18] Bartholdi L., Grigorchuk R., Nekrashevych V., “From fractal groups to fractal sets”, Fractals in Graz 2001: Analysis, dynamics, geometry, stochastics, Trends Math., Birkhäuser, Basel, 2003, 25–118 | MR | Zbl

[19] Bartholdi L., Grigorchuk R.I., Šuniḱ Z., “Branch groups”, Handbook of algebra, 3, North-Holland, Amsterdam, 2003, 989–1112 | DOI | MR

[20] Bartholdi L., Kaimanovich V.A., Nekrashevych V.V., “On amenability of automata groups”, Duke Math. J., 154:3 (2010), 575–598, arXiv: 0802.2837 [math.GR] | DOI | MR | Zbl

[21] Bartholdi L., Reznykov I.I., Sushchansky V.I., “The smallest Mealy automaton of intermediate growth”, J. Algebra, 295:2 (2006), 387–414 | DOI | MR | Zbl

[22] Bartholdi L., Šuniḱ Z., “Some solvable automaton groups”, Topological and asymptotic aspects of group theory, Contemp. Math., 394, Amer. Math. Soc., Providence, RI, 2006, 11–29 | DOI | MR | Zbl

[23] Bartholdi L., Virág B., “Amenability via random walks”, Duke Math. J., 130:1 (2005), 39–56, arXiv: math/0305262 [math.GR] | DOI | MR | Zbl

[24] Bekka B., de la Harpe P., Valette A., Kazhdan's property (T), New Math. Monogr., 11, Cambridge Univ. Press, Cambridge, 2008 | MR | Zbl

[25] Bekka M.B., Louvet N., “Some properties of $C^*$-algebras associated to discrete linear groups”, $C^*$-algebras, Proc. SFB Workshop (Münster (Germany), 1999), Springer, Berlin, 2000, 1–22 | MR | Zbl

[26] Benjamini I., Hoffman C., “$\omega $-Periodic graphs”, Electron. J. Comb., 12 (2005), 46 | MR | Zbl

[27] Benjamini I., Schramm O., “Recurrence of distributional limits of finite planar graphs”, Electron. J. Probab., 6 (2001), 23, arXiv: math/0011019 [math.PR] | DOI | MR | Zbl

[28] Bergeron N., Gaboriau D., “Asymptotique des nombres de Betti, invariants $l^2$ et laminations”, Comment. Math. Helv., 79:2 (2004), 362–395 | DOI | MR | Zbl

[29] Bhattacharjee M., “The probability of generating certain profinite groups by two elements”, Isr. J. Math., 86:1–3 (1994), 311–329 | DOI | MR | Zbl

[30] Bogolyubov M.M., “Pro deyaki ergodichni vlastivosti sutsilnikh grup peretvoren”, Nauk. zap. Kiïv. derzh. univ. im. T.G. Shevchenka. Fiz.-mat. zb., 4:5 (1939), 45–52; Боголюбов Н.Н., “О некоторых эргодических свойствах непрерывных групп преобразований”, Избр. тр., т. 1, Наук. думка, Киев, 1969, 561–569

[31] Bondarenko I., Groups generated by bounded automata and their Schreier graphs, PhD Dissertation, Texas A Univ., College Station, TX, 2007 | MR

[32] Bondarenko I.V., “Finite generation of iterated wreath products”, Arch. Math., 95:4 (2010), 301–308 | DOI | MR | Zbl

[33] Bondarenko I.V., Growth of Schreier graphs of automaton groups, E-print, 2011, arXiv: 1101.3200 [math.GR]

[34] Bondarenko I., D'Angeli D., Nagnibeda T., Ends of Schreier graphs of self-similar groups, Preprint, 2011 http://www.unige.ch/~tatiana/Publ/EndsSchreier\textunderscore www.pdf

[35] Bondarenko I., Grigorchuk R., Kravchenko R., Muntyan Y., Nekrashevych V., Savchuk D., Šunić Z., “On classification of groups generated by 3-state automata over a 2-letter alphabet”, Algebra and Discrete Math., 2008, no. 1, 1–163, arXiv: 0803.3555 [math.GR] | MR | Zbl

[36] Bożejko M., Dykema K., Lehner F., “Isomorphisms of Cayley graphs of surface groups”, Algebra and Discrete Math., 2006, no. 1, 18–37 | MR

[37] Brin M.G., Squier C.C., “Groups of piecewise linear homeomorphisms of the real line”, Invent. math., 79:3 (1985), 485–498 | DOI | MR | Zbl

[38] Cannon J.W., Floyd W.J., Parry W.R., “Introductory notes on Richard Thompson's groups”, Enseign. Math. Sér. 2, 42:3–4 (1996), 215–256 | MR | Zbl

[39] Ceccherini-Silberstein T., Coornaert M., Cellular automata and groups, Springer Monogr. Math., Springer, Berlin, 2010 | DOI | MR | Zbl

[40] Ceccherini-Silberstein T., Elek G., “Minimal topological actions do not determine the measurable orbit equivalence class”, Groups, Geom., and Dyn., 2:2 (2008), 139–163 | DOI | MR | Zbl

[41] Ceccherini-Silberstein T., Grigorchuk R., de la Harpe P., “Amenability and paradoxical decompositions for pseudogroups and discrete metric spaces”, Proc. Steklov Inst. Math., 224 (1999), 57–97 | MR | Zbl

[42] Chabauty C., “Limite d'ensembles et géométrie des nombres”, Bull. Soc. math. France., 78 (1950), 143–151 | MR | Zbl

[43] Champetier C., “L'espace des groupes de type fini”, Topology, 39:4 (2000), 657–680 | DOI | MR | Zbl

[44] Champetier C., Guirardel V., “Limit groups as limits of free groups”, Isr. J. Math., 146 (2005), 1–75 | DOI | MR | Zbl

[45] Chou C., “Elementary amenable groups”, Ill. J. Math., 24:3 (1980), 396–407 | MR | Zbl

[46] Connes A., Noncommutative geometry, Acad. Press, San Diego, CA, 1994 | MR | Zbl

[47] Connes A., Feldman J., Weiss B., “An amenable equivalence relation is generated by a single transformation”, Ergodic Theory and Dyn. Syst., 1:4 (1981), 431–450 | DOI | MR | Zbl

[48] D'Angeli D., Donno A., Matter M., Nagnibeda T., “Schreier graphs of the Basilica group”, J. Mod. Dyn., 4:1 (2010), 167–205, arXiv: 0911.2915 [math.GR] | DOI | MR | Zbl

[49] D'Angeli D., Donno A., Nagnibeda T., Partition functions of the Ising model on some self-similar Schreier graphs, E-print, 2010, arXiv: 1003.0611 [math.GR]

[50] Davidoff G., Sarnak P., Valette A., Elementary number theory, group theory, and Ramanujan graphs, LMS Stud. Texts, 55, Cambridge Univ. Press, Cambridge, 2003 | MR | Zbl

[51] Davidson K.R., $C^*$-algebras by example, Fields Inst. Monogr., 6, Amer. Math. Soc., Providence, RI, 1996 | MR | Zbl

[52] Day M.M., “Amenable semigroups”, Ill. J. Math., 1 (1957), 509–544 | MR | Zbl

[53] Dixmier J., Les $C^*$-algèbres et leurs représentations, Grands Classiq. Gauthier-Villars, J. Gabay, Paris, 1996 | MR

[54] Dixon J.D., du Sautoy M.P.F., Mann A., Segal D., Analytic pro-$p$ groups, Cambridge Stud. Adv. Math., 61, 2nd ed., Cambridge Univ. Press, Cambridge, 1999 | MR | Zbl

[55] Dye H.A., “On groups of measure preserving transformations. I, II”, Amer. J. Math., 81 (1959), 119–159 ; Amer. J. Math., 85 (1963), 551–576 | DOI | MR | Zbl | DOI | MR | Zbl

[56] Eilenberg S., Automata, languages, and machines, Pure and Appl. Math., 58, Acad. Press, New York, 1974 | MR | Zbl

[57] Farber M., “Geometry of growth: approximation theorems for $L^2$ invariants”, Math. Ann., 311:2 (1998), 335–375 | DOI | MR | Zbl

[58] Feldman J., Moore C.C., “Ergodic equivalence relations, cohomology, and von Neumann algebras. I”, Trans. Amer. Math. Soc., 234:2 (1977), 289–324 | DOI | MR | Zbl

[59] Figà-Talamanca A., “Diffusion on compact ultrametric spaces”, Noncompact Lie groups and some of their applications, Proc. NATO Adv. Res. Workshop (San Antonio, TX, 1993), NATO Adv. Sci. Inst. C: Math. and Phys. Sci., 429, Kluwer, Dordrecht, 1994, 157–167 | MR | Zbl

[60] Følner E., “Note on groups with and without full Banach mean value”, Math. scand., 5 (1957), 5–11 | MR

[61] Furman A., “Gromov's measure equivalence and rigidity of higher rank lattices”, Ann. Math. Ser. 2, 150:3 (1999), 1059–1081 | DOI | MR | Zbl

[62] Furman A., A survey of measured group theory, E-print, 2009, arXiv: 0901.0678 [math.DS]

[63] Gaboriau D., “Coût des relations d'équivalence et des groupes”, Invent. math., 139:1 (2000), 41–98 | DOI | MR | Zbl

[64] Gaboriau D., “Invariants $l^2$ de relations d'équivalence et de groupes”, Publ. Math. IHES, 95 (2002), 93–150 | DOI | MR | Zbl

[65] Gefen Y., Aharony A., Mandelbrot B.B., “Phase transitions on fractals. I: Quasi-linear lattices”, J. Phys. A, 16:6 (1983), 1267–1278 | DOI | MR

[66] Gelander T., Glasner Y., “Countable primitive groups”, Geom. and Funct. Anal., 17:5 (2008), 1479–1523 | DOI | MR | Zbl

[67] Glasner E.\, Ergodic theory via joinings, Math. Surv. and Monogr., 101, Amer. Math. Soc., Providence, RI, 2003 | DOI | MR | Zbl

[68] Glasner Y., Mozes S., “Automata and square complexes”, Geom. Dedicata., 111 (2005), 43–64 | DOI | MR | Zbl

[69] Greenleaf F.P., Invariant means on topological groups and their applications, Van Nostrand Math. Stud., 16, Van Nostrand Reinhold Co., New York, 1969 | MR | Zbl

[70] Grigorchuk R.I., “K probleme Bernsaida o periodicheskikh gruppakh”, Funkts. analiz i ego pril., 14:1 (1980), 53–54 | MR | Zbl

[71] Grigorchuk R.I., “K probleme Milnora o gruppovom roste”, DAN SSSR, 271:1 (1983), 30–33 | MR | Zbl

[72] Grigorchuk R.I., “Stepeni rosta konechno-porozhdennykh grupp i teoriya invariantnykh srednikh”, Izv. AN SSSR. Ser. mat., 48:5 (1984), 939–985 | MR

[73] Grigorchuk R.I., “O stepenyakh rosta $p$-grupp i grupp bez krucheniya”, Mat. sb., 126:2 (1985), 194–214 | MR | Zbl

[74] Grigorchuk R.I., “Svyaz mezhdu algoritmicheskimi problemami i entropiinymi kharakteristikami grupp”, DAN SSSR, 284:1 (1985), 24–29 | MR | Zbl

[75] Grigorchuk R.I., “O polugruppakh s sokrascheniyami stepennogo rosta”, Mat. zametki, 43:3 (1988), 305–319 | MR

[76] Grigorchuk R.I., “O ryade Gilberta–Puankare graduirovannykh algebr, assotsiirovannykh s gruppami”, Mat. sb., 180:2 (1989), 207–225 | MR

[77] Grigorchuk R.I., “Primer konechno opredelennoi amenabelnoi gruppy, ne prinadlezhaschei klassu $EG$”, Mat. sb., 189:1 (1998), 79–100 | DOI | MR | Zbl

[78] Grigorchuk R.I., “On the system of defining relations and the Schur multiplier of periodic groups generated by finite automata”, Groups St. Andrews 1997 in Bath, v. 1, LMS Lect. Note Ser., 260, Cambridge Univ. Press, Cambridge, 1999, 290–317 | MR | Zbl

[79] Grigorchuk R.I., “Vetvyaschiesya gruppy”, Mat. zametki, 67:6 (2000), 852–858 | DOI | MR | Zbl

[80] Grigorchuk R.I., “Just infinite branch groups”, New horizons in pro-$p$ groups, Prog. Math., 184, Birkhäuser, Boston, MA, 2000, 121–179 | MR | Zbl

[81] Grigorchuk R., “Solved and unsolved problems around one group”, Infinite groups: geometric, combinatorial and dynamical aspects, Prog. Math., 248, Birkhäuser, Basel, 2005, 117–218 | DOI | MR | Zbl

[82] Grigorchuk R.I., Herfort W.N., Zalesskii P.A., “The profinite completion of certain torsion $p$-groups”, Algebra, Proc. Intern. Conf. (Moscow, 1998), W. de Gruyter, Berlin, 2000, 113–123 | MR | Zbl

[83] Grigorchuk R., Kaimanovich V.A., Nagnibeda T., Ergodic properties of boundary actions and Nielsen–Schreier theory, E-print, 2009, arXiv: 0901.4734 [math.GR]

[84] Grigorchuk R.I., Linnell P., Schick T., Żuk A., “On a question of Atiyah”, C. r. Acad. sci. Paris. Sér. 1: Math., 331:9 (2000), 663–668 | DOI | MR | Zbl

[85] Grigorchuk R., Medynets K., On simple finitely generated amenable groups, E-print, 2011, arXiv: 1105.0719 [math.GR]

[86] Grigorhuk R., Nekrashevych V., “Self-similar groups, operator algebras and Schur complement”, J. Mod. Dyn., 1:3 (2007), 323–370 | DOI | MR

[87] Grigorchuk R.I., Nekrashevich V.V., Suschanskii V.I., “Avtomaty, dinamicheskie sistemy i gruppy”, Tr. MIAN, 231, 2000, 134–214 | MR | Zbl

[88] Grigorchuk R., Nekrashevych V., Šunić Z., “Hanoi Towers groups”, Oberwolfach Rep., 3:2 (2006), 1179–1182, Rep. 19: Topological and geometric methods in group theory

[89] Grigorchuk R.I., Nekrashevych V., Šunić Z., “Hanoi Towers group on 3 pegs and its pro-finite closure”, Oberwolfach Rep., 3:2 (2006), 1477–1479, Rep. 25: Pro-$p$ extensions of global fields and pro-$p$ groups

[90] Grigorchuk R., Pak I., “Groups of intermediate growth: an introduction”, Enseign. Math. Sér. 2, 54:3–4 (2008), 251–272 | MR | Zbl

[91] Grigorchuk R., Šuniḱ Z., “Asymptotic aspects of Schreier graphs and Hanoi Towers groups”, C. r. Math. Acad. sci. Paris, 342:8 (2006), 545–550 | DOI | MR | Zbl

[92] Grigorchuk R., Šunić Z., “Self-similarity and branching in group theory”, Groups St. Andrews 2005, LMS Lect. Note Ser., 1, Cambridge Univ. Press, Cambridge, 2007, 36–95 | MR

[93] Grigorchuk R., Šunić Z., “Schreier spectrum of the Hanoi Towers group on three pegs”, Analysis on graphs and its applications, Proc. Symp. Pure Math., 77, Amer. Math. Soc., Providence, RI, 2008, 183–198 | DOI | MR | Zbl

[94] Grigorchuk R.I., Żuk A., “On the asymptotic spectrum of random walks on infinite families of graphs”, Random walks and discrete potential theory, Proc. Conf. (Cortona, 1997), Symp. Math., 39, Cambridge Univ. Press, Cambridge, 1999, 188–204 | MR | Zbl

[95] Grigorchuk R.I., Żuk A., “The lamplighter group as a group generated by a 2-state automaton, and its spectrum”, Geom. Dedicata, 87:1–3 (2001), 209–244 | DOI | MR | Zbl

[96] Grigorchuk R.I., Żuk A., “On a torsion-free weakly branch group defined by a three state automaton”, Intern. J. Algebra and Comput., 12:1–2 (2002), 223–246 | DOI | MR | Zbl

[97] Grigorchuk R.I., Żuk A., “Spectral properties of a torsion-free weakly branch group defined by a three state automaton”, Computational and statistical group theory, Proc. AMS Spec. Session (Las Vegas, NV/Hoboken, NJ, 2001), Contemp. Math., 298, Amer. Math. Soc., Providence, RI, 2002, 57–82 | DOI | MR | Zbl

[98] Grigorchuk R.I., Żuk A., “The Ihara zeta function of infinite graphs, the KNS spectral measure and integrable maps”, Random walks and geometry, W. de Gruyter, Berlin, 2004, 141–180 | MR | Zbl

[99] Gupta N., Sidki S., “On the Burnside problem for periodic groups”, Math. Ztschr., 182:3 (1983), 385–388 | DOI | MR | Zbl

[100] de la Harpe P., Topics in geometric group theory, Chicago Lect. Math., Univ. Chicago Press, Chicago, 2000 | MR

[101] Higman G., Finitely presented infinite simple groups, Notes Pure Math., 8, Dept. Pure Math., Dept. Math., I.A.S., Australian National Univ., Canberra, 1974 | MR

[102] Hinz A.M., “The tower of Hanoi”, Enseign. Math. Sér. 2, 35:3–4 (1989), 289–321 | MR | Zbl

[103] Hjorth G., “A converse to Dye's theorem”, Trans. Amer. Math. Soc., 357:8 (2005), 3083–3103 | DOI | MR | Zbl

[104] Hopcroft J.E., Ullman J.D., Introduction to automata theory, languages, and computation, Addison–Wesley Ser. Comput. Sci., Addison–Wesley, Reading, MA, 1979 | MR | Zbl

[105] Jackson S., Kechris A.S., Louveau A., “Countable Borel equivalence relations”, J. Math. Log., 2:1 (2002), 1–80 | DOI | MR | Zbl

[106] Kaimanovich V.A., “Amenability, hyperfiniteness, and isoperimetric inequalities”, C. r. Acad. sci. Paris. Sér. 1: Math., 325:9 (1997), 999–1004 | DOI | MR | Zbl

[107] Kaimanovich V.A., “Hausdorff dimension of the harmonic measure on trees”, Ergodic Theory and Dyn. Syst., 18 (1998), 631–660 | DOI | MR | Zbl

[108] Kaimanovich V.A., “Random walks on Sierpinski graphs: Hyperbolicity and stochastic homogenization”, Fractals in Graz 2001: Analysis, dynamics, geometry, stochastics, Trends Math., Birkhäuser, Basel, 2003, 145–183 | MR | Zbl

[109] Kaimanovich V.A., ““Münchhausen trick” and amenability of self-similar groups”, Intern. J. Algebra and Comput., 15:5–6 (2005), 907–937 | DOI | MR | Zbl

[110] Kaimanovich V.A., Sobieczky F., “Stochastic homogenization of horospheric tree products”, Probabilistic approach to geometry, Adv. Stud. Pure Math., 57, Math. Soc. Japan, Tokyo, 2010, 199–229 | MR | Zbl

[111] Kaimanovich V.A., Vershik A.M., “Random walks on discrete groups: Boundary and entropy”, Ann. Probab., 11:3 (1983), 457–490 | DOI | MR | Zbl

[112] Kambites M., Silva P.V., Steinberg B., “The spectra of lamplighter groups and Cayley machines”, Geom. Dedicata, 120 (2006), 193–227 | DOI | MR | Zbl

[113] Kechris A.S., Miller B.D., Topics in orbit equivalence, Lect. Notes Math., 1852, Springer, Berlin, 2004 | DOI | MR | Zbl

[114] Kechris A.S., Tsankov T., “Amenable actions and almost invariant sets”, Proc. Amer. Math. Soc., 136:2 (2008), 687–697 | DOI | MR | Zbl

[115] Kesten H., “Full Banach mean values on countable groups”, Math. scand., 7 (1959), 146–156 | MR | Zbl

[116] Kesten H., “Symmetric random walks on groups”, Trans. Amer. Math. Soc., 92 (1959), 336–354 | DOI | MR | Zbl

[117] Kigami J., Analysis on fractals, Cambridge Tracts Math., 143, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

[118] Kuchment P., “Quantum graphs: an introduction and a brief survey”, Analysis on graphs and its applications, Proc. Symp. Pure Math., 77, Amer. Math. Soc., Providence, RI, 2008, 291–312 | DOI | MR | Zbl

[119] Kudryavtsev V.B., Aleshin S.V., Podkolzin A.S., Vvedenie v teoriyu avtomatov, Nauka, M., 1985 | MR

[120] Kuratowski K., Topology, v. 1, Acad. Press, New York, 1966 | MR | Zbl

[121] Lackenby M., “Expanders, rank and graphs of groups”, Isr. J. Math., 146 (2005), 357–370 | DOI | MR | Zbl

[122] Lackenby M., “Heegaard splittings, the virtually Haken conjecture and property $(\tau )$”, Invent. math., 164:2 (2006), 317–359 | DOI | MR | Zbl

[123] Leonov Yu.G., “Problema sopryazhennosti v odnom klasse 2-grupp”, Mat. zametki, 64:4 (1998), 573–583 | DOI | MR | Zbl

[124] Levitt G., “On the cost of generating an equivalence relation”, Ergodic Theory and Dyn. Syst., 15:6 (1995), 1173–1181 | DOI | MR | Zbl

[125] Lubotzky A., With an appendix by J.D. Rogawski, Prog. Math., 125, Birkhäuser, Basel, 1994 | MR

[126] Lubotzky A., “Cayley graphs: eigenvalues, expanders and random walks”, Surveys in combinatorics, 1995, Proc. Conf. (Stirling (UK), 1995), LMS Lect. Note Ser., 218, Cambridge Univ. Press, Cambridge, 1995, 155–189 | MR | Zbl

[127] Lubotzky A., Phillips R., Sarnak P., “Ramanujan graphs”, Combinatorica, 8:3 (1988), 261–277 | DOI | MR | Zbl

[128] Lyndon R.C., Schupp P.E., Combinatorial group theory, Ergebn. Math. und ihrer Grenzgeb., 89, Springer, Berlin, 1977 | MR | Zbl

[129] Lysënok I.G., “Sistema opredelyayuschikh sootnoshenii dlya gruppy Grigorchuka”, Mat. zametki, 38:4 (1985), 503–516 | MR | Zbl

[130] Lysenok I., Myasnikov A., Ushakov A., “The conjugacy problem in the Grigorchuk group is polynomial time decidable”, Groups, Geom., and Dyn., 4:4 (2010), 813–833 | DOI | MR | Zbl

[131] Mackey G.W., “Ergodic transformation groups with a pure point spectrum”, Ill. J. Math., 8 (1964), 593–600 | MR | Zbl

[132] Mackey G.W., The theory of unitary group representations, Chicago Lect. Math., Univ. Chicago Press, Chicago, 1976 | MR | Zbl

[133] Margulis G.A., “Yavnye konstruktsii rasshiritelei”, Probl. peredachi inform., 9:4 (1973), 71–80 | MR | Zbl

[134] Massey W.S., Algebraic topology: An introduction, Grad. Texts Math., 56, Springer, New York, 1977 | MR | Zbl

[135] Matter M., Nagnibeda T., Abelian sandpile model on randomly rooted graphs and self-similar groups, E-print, 2011, arXiv: 1105.4036 [math.PR]

[136] McKay B.D., “The expected eigenvalue distribution of a large regular graph”, Linear Algebra and Appl., 40 (1981), 203–216 | DOI | MR | Zbl

[137] Meier J., Groups, graphs and trees: An introduction to the geometry of infinite groups, LMS Stud. Texts, 73, Cambridge Univ. Press, Cambridge, 2008 | MR | Zbl

[138] Mikhailova K.A., “Problema vkhozhdeniya dlya pryamykh proizvedenii grupp”, DAN SSSR, 119:6 (1958), 1103–1105 | Zbl

[139] Muntyan Y., Automata groups, PhD Dissertation, Texas A Univ., College Station, TX, 2009

[140] Nagnibeda T., “Random walks, spectral radii, and Ramanujan graphs”, Random walks and geometry, W. de Gruyter, Berlin, 2004, 487–500 | MR | Zbl

[141] Nekrashevych V.V., “Cuntz–Pimsner algebras of group actions”, J. Oper. Theory, 52:2 (2004), 223–249 | MR

[142] Nekrashevych V., Self-similar groups, Math. Surv. and Monogr., 117, Amer. Math. Soc., Providence, RI, 2005 | DOI | MR | Zbl

[143] Nekrashevych V.V., “Free subgroups in groups acting on rooted trees”, Groups, Geom., and Dyn., 4:4 (2010), 847–862, arXiv: 0802.2554 [math.GR] | DOI | MR | Zbl

[144] Nekrashevych V., Combinatorial models of expanding dynamical systems, E-print, 2008, arXiv: 0810.4936 [math.DS]

[145] Nekrashevych V.V., Pete G., “Scale-invariant groups”, Groups, Geom., and Dyn., 5:1 (2011), 139–167, arXiv: 0811.0220 [math.GR] | DOI | MR | Zbl

[146] Nekrashevych V., Teplyaev A., “Groups and analysis on fractals”, Analysis on graphs and its applications, Proc. Symp. Pure Math., 77, Amer. Math. Soc., Providence, RI, 2008, 143–180 | DOI | MR | Zbl

[147] von Neumann J., “Zur allgemeinen Theorie des Masses”, Fund. math., 13 (1929), 73–116 | Zbl

[148] Olshanskii A.Yu., “Beskonechnaya prostaya nëterova gruppa bez krucheniya”, Izv. AN SSSR. Ser. mat., 43:6 (1979), 1328–1393 | MR

[149] Olshanskii A.Yu., “K voprosu o suschestvovanii invariantnogo srednego na gruppe”, UMN, 35:4 (1980), 199–200 | MR

[150] Ornstein D.S., Weiss B., “Ergodic theory of amenable group actions. I: The Rohlin lemma”, Bull. Amer. Math. Soc., 2:1 (1980), 161–164 | DOI | MR | Zbl

[151] Osin D., “Rank gradient and torsion groups”, Bull. London Math. Soc., 43 (2011), 10–16, arXiv: 0905.1322 [math.GR] | DOI | MR | Zbl

[152] Pervova E.L., “Vsyudu plotnye podgruppy odnoi gruppy avtomorfizmov dereva”, Tr. MIAN, 231, 2000, 356–367 | MR | Zbl

[153] Pervova E.L., “Kongruents-svoistvo AT-grupp”, Algebra i logika, 41:5 (2002), 553–567 | MR | Zbl

[154] Pervova E., “Profinite completions of some groups acting on trees”, J. Algebra, 310:2 (2007), 858–879 | DOI | MR | Zbl

[155] Previte J.P., “Graph substitutions”, Ergodic Theory and Dyn. Syst., 18:3 (1998), 661–685 | DOI | MR | Zbl

[156] Previte M., Yang S., “A novel way to generate fractals”, Amer. Math. Mon., 115:1 (2008), 13–32 | MR | Zbl

[157] Quint J.-F., “Harmonic analysis on the Pascal graph”, J. Funct. Anal., 256:10 (2009), 3409–3460 | DOI | MR | Zbl

[158] Raghunathan M.S., Discrete subgroups of Lie groups, Ergebn. Math. und ihrer Grenzgeb., 68, Springer, Berlin, 1972 | MR | Zbl

[159] Rokhlin V.A., “Ob osnovnykh ponyatiyakh teorii mery”, Mat. sb., 25:1 (1949), 107–150 ; Rohlin V.A., On the fundamental ideas of measure theory, AMS Transl., 71, Amer. Math. Soc., Providence, RI, 1952 | Zbl | MR

[160] Rozhkov A.V., “Tsentralizatory elementov v odnoi gruppe avtomorfizmov derevev”, Izv. RAN. Ser. mat., 57:6 (1993), 82–105 | MR | Zbl

[161] Rozhkov A.V., “Problema sopryazhennosti v odnoi gruppe avtomorfizmov beskonechnogo dereva”, Mat. zametki, 64:4 (1998), 592–597 | DOI | MR | Zbl

[162] Rubin M., “On the reconstruction of topological spaces from their groups of homeomorphisms”, Trans. Amer. Math. Soc., 312:2 (1989), 487–538 | DOI | MR | Zbl

[163] Savchuk D.M., “On word problem in contracting automorphism groups of rooted trees”, Visn. Kiïv. univ. Ser.: Fiz.-mat. nauki, 2003, no. 1, 51–56 | MR | Zbl

[164] Savchuk D., Asymptotic, algorithmic and geometric aspects of groups generated by automata, PhD Dissertation, Texas A Univ., College Station, TX, 2009 | MR

[165] Savchuk D., “Some graphs related to Thompson's group $F$”, Combinatorial and geometric group theory, Trends Math., Birkhäuser, Basel, 2010, 279–296 | MR | Zbl

[166] Savchuk D., Schreier graphs of actions of Thompson's group $F$ on the unit interval and on the Cantor set, E-print, 2011, arXiv: 1105.4017 [math.GR]

[167] Serre J.-P., “Répartition asymptotique des valeurs propres de l'opérateur de Hecke $T_p$”, J. Amer. Math. Soc., 10:1 (1997), 75–102 | DOI | MR | Zbl

[168] Serre J.-P., Trees, Springer Monogr. Math., Springer, Berlin, 2003 | MR

[169] Shalev A., “Subgroup structure, fractal dimension, and Kac–Moody algebras”, Groups and geometries, Proc. Conf. (Siena, 1996), Trends Math., Birkhäuser, Basel, 1998, 163–176 | MR | Zbl

[170] Shalom Y., “Rigidity of commensurators and irreducible lattices”, Invent. math., 141:1 (2000), 1–54 | DOI | MR | Zbl

[171] Shavgulidze E.T., “The Thompson group $F$ is amenable”, Infin. Dimens. Anal., Quantum Probab. and Relat. Top., 12:2 (2009), 173–191 | DOI | MR | Zbl

[172] Sidki S., “Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity”, J. Math. Sci., 100:1 (2000), 1925–1943 | DOI | MR | Zbl

[173] Slaman T.A., Steel J.R., “Definable functions on degrees”, Cabal Seminar 81–85, Lect. Notes Math., 1333, Springer, Berlin, 1988, 37–55 | DOI | MR

[174] Strichartz R.S., “Analysis on fractals”, Notices Amer. Math. Soc., 46:10 (1999), 1199–1208 | MR | Zbl

[175] Šunić Z., “Hausdorff dimension in a family of self-similar groups”, Geom. Dedicata, 124 (2007), 213–236 | DOI | MR | Zbl

[176] Šunić Z., Pattern closure of groups of tree automorphisms, E-print, 2010, arXiv: 1012.1688 [math.GR] | Zbl

[177] Šunić Z., Ventura E., The conjugacy problem is not solvable in automaton groups, E-print, 2010, arXiv: 1010.1993 [math.GR] | Zbl

[178] Szegedy M., “In how many steps the $k$ peg version of the Towers of Hanoi game can be solved?”, STACS 99, Proc. Symp. (Trier (Germany), 1999), Lect. Notes Comput. Sci., 1563, Springer, Berlin, 1999, 356–361 | DOI | MR

[179] Takesaki M., Theory of operator algebras. I, Encycl. Math. Sci., 124, Operator Algebras and Non-commutative Geometry. V, Springer, Berlin, 2002 | MR | Zbl

[180] Takesaki M., Theory of operator algebras. II, Encycl. Math. Sci., 125, Operator Algebras and Non-commutative Geometry. VI, Springer, Berlin, 2003 | MR | Zbl

[181] Takesaki M., Theory of operator algebras. III, Encycl. Math. Sci., 127, Operator Algebras and Non-commutative Geometry. VIII, Springer, Berlin, 2003 | MR | Zbl

[182] Teplyaev A., “Harmonic coordinates on fractals with finitely ramified cell structure”, Can. J. Math., 60:2 (2008), 457–480 | DOI | MR | Zbl

[183] Topics in representation theory, Adv. Sov. Math., 2, eds. Ed. by A.A. Kirillov, Amer. Math. Soc., Providence, RI, 1991

[184] Vershik A.M., Nonfree actions of countable groups and their characters, E-print, 2010, arXiv: 1012.4604 [math.DS] | MR

[185] Vershik A.M., Kerov S.V., “Kharaktery i faktor-predstavleniya beskonechnoi simmetricheskoi gruppy”, DAN SSSR, 257:5 (1981), 1037–1040 | MR | Zbl

[186] Vorobets M., Vorobets Ya., “On a free group of transformations defined by an automaton”, Geom. Dedicata, 124 (2007), 237–249 | DOI | MR | Zbl

[187] Vorobets M., Vorobets Ya., “On a series of finite automata defining free transformation groups”, Groups, Geom., and Dyn., 4:2 (2010), 377–405 | DOI | MR | Zbl

[188] Vorobets Ya., Notes on the Schreier graphs of the Grigorchuk group, Preprint, 2011 http://www.math.tamu.edu/~yvorobet/Research/Schreier.pdf

[189] Wagon S., The Banach–Tarski paradox, Cambridge Univ. Press, Cambridge, 1993 | MR

[190] Weiss B., “Measurable dynamics”, Conference in modern analysis and probability (New Haven, CT, 1982), Contemp. Math., 26, Amer. Math. Soc., Providence, RI, 1984, 395–421 | DOI | MR

[191] Wilson J.S., “Groups with every proper quotient finite”, Proc. Cambridge Philos. Soc., 69 (1971), 373–391 | DOI | MR | Zbl

[192] Wilson J.S., Profinite groups, LMS Monogr. New Ser., 19, Clarendon Press, Oxford, 1998 | MR

[193] Wilson J.S., “On just infinite abstract and profinite groups”, New horizons in pro-$p$ groups, Prog. Math., 184, Birkhäuser, Boston, MA, 2000, 181–203 | MR | Zbl

[194] Wormald N.C., “Models of random regular graphs”, Surveys in combinatorics, 1999, Proc. Conf. (Canterbury, 1999), LMS Lect. Note Ser., 267, Cambridge Univ. Press, Cambridge, 1999, 239–298 | MR | Zbl

[195] Yu G., “The coarse Baum–Connes conjecture for spaces which admit a uniform embedding into Hilbert space”, Invent. math., 139:1 (2000), 201–240 | DOI | MR | Zbl

[196] ZalesskiĭA.E., “Group rings of simple locally finite groups”, Finite and locally finite groups (Istanbul, 1994), NATO Adv. Sci. Inst. C: Math. and Phys. Sci., 471, Kluwer, Dordrecht, 1995, 219–246 | MR | Zbl

[197] Zimmer R.J., Ergodic theory and semisimple groups, Monogr. Math., 81, Birkhäuser, Basel, 1984 | MR | Zbl