Shreier graphs of iterated monodromy groups of sub-hyperbolic quadratic polynomials (in Ukrainian)

Ye. V. Bondarenko

We study Shreier graphs of iterated monodromy groups of sub"=hyperbolic quadratic polynomials. The substitutional rules for constructing Shreier graphs on levels are given. An efficient method is proposed for calculating the orbital contracting coefficient of the groups as $\lambda^{-1}$, where $\lambda$ is the Perron number of some nonnegative integral matrix. An efficient method is given for finding the growth of diameters of Shreier graphs on levels. Finally, we give the boundaries, where the growth degrees of orbital Shreier graphs are located. The first examples of groups which act on a binary tree and which have the orbital Shreier graphs of growth degree $\frac{\log 2}{\log\lambda}$ where $\lambda$ is irrational number, are indicated. The first example of a group with orbital contracting coefficient (and thus general contracting coefficient) that does not determine the growth of diameters and growth of orbital Shreier graphs is constructed.

1. Островский А.~М. Решение уравнений и систем уравнений.-- Москва: Изд. иностр. лит., 1963. -- 219~с.

2. Гантмахер Ф.~Р. Теория матриц.-- Москва: Наука, 1966. -- 576 с.

3. Валеев К.~Г. Расщепление спектра матриц.-- Киев: Вища Школа, 1986. -- 269 с.

4. Гайдуш И.~В. Системы с дискретным временем.-- Минск: Ин-т мат. НАН Беларуси, 2001.

5. Bartholdi L. Counting path in graphs // Enseignement Math.-- 1999.-- V.45.-- P.83--131.

6. Bartholdi L., Ceccherini-Silberstein T.~G. Growth series and random walks on some hyperbolic graphs.-- Preprint, 2001. -- 22 p.

7. Bartholdi L., Grigorchuk R. On the spectrum of Hecke type operators related to some fractal groups. Proc. of the Steklov Institute of Mathematics.-- 2000.-- V.231.-- P.5--45.

8. Bartholdi L., Nekrashevych V. Iterated monodromy groups of quadratic polynomials.-- Preprint, 2003.

9. Gaubert S., Gunawardena J. The Perron-Frobenius theorem for homogeneous, monotone functions.-- Preprint, 2003.-- 20 p.

10. Grigorchuk R., \.Zuk A. On the asymptotic spectrum of random walks on infinite families of graphs. In M.~Picardello and W.~Woess, editors, Proceedings of the Conference ``Random Walks and Discrete Potential Theory'', (Cortona), № 22 in Symposia Mathematica, p. 188--204. Cambridge University Press, 1999.

11. Grigorchuk R., \.Zuk A. The lamplighter group as a group generated by a $2$-state automaton and its spectrum // Geom. Dedicata 87, 1-3 (2001), 209--244.

12. Grigorchuk R., \.Zuk A. The Ihara zeta function of infinite graphs, the KNS spectral measure and integrable maps // Proc. of the Conference "Random walks in Vienne", to appear, 2003.-- 39 p.

13. Kr\"on R. Growth of self-similar graphs.-- Vienna: Preprint ESI 1125, 2002.-- 14 p.

14. Bartholdi L., Grigorchuk R., Nekrashevych V. From fractal groups to fractal sets. In Peter Grabner and Wolfgang Woess, editors, Fractals in Graz 2001. Analysis -- Dynamics -- Geometry -- Stochastics, P.25--118, 2003.

15. Nekrashevych V. Iterated monodromy group.-- Preprint, Geneva University, 2002.-- 31~p.

16. Nekrashevych V. Limit spaces of self-similar group actions.-- Preprint, Geneva University, 2002.-- 33~p.

17. Nekrashevych V. Virtual endomorphism of groups // Algebra and Discrete Mathematics.-- 2002.-- V.1, № 1.-- P. 96--136.

18. Previte J.~P. Graph substitutions // Ergodic Theory Dynam. Systems.-- 1998.-- V.18, № 3.-- P. 661--685.

19. Nekrashevych V., Grigorchuk R., Sushchanskii V.I. Automata, dynamical systems and groups // Proc. of the Steklov Institute of Mathematics.-- 2000.-- V.231.-- P. 128--203.

20. Woess W. Random walks on infinite graphs and groups // Cambridge Tracts in Mathematics, 138.-- Cambridge University Press, 1999.

	Shreier graphs of iterated monodromy groups of sub-hyperbolic quadratic polynomials (in Ukrainian)
Author	Ye. V. Bondarenko bond@mail.univ.kiev.ua Taras Shevchenko National University of Kyiv
Abstract	We study Shreier graphs of iterated monodromy groups of sub"=hyperbolic quadratic polynomials. The substitutional rules for constructing Shreier graphs on levels are given. An efficient method is proposed for calculating the orbital contracting coefficient of the groups as $\lambda^{-1}$, where $\lambda$ is the Perron number of some nonnegative integral matrix. An efficient method is given for finding the growth of diameters of Shreier graphs on levels. Finally, we give the boundaries, where the growth degrees of orbital Shreier graphs are located. The first examples of groups which act on a binary tree and which have the orbital Shreier graphs of growth degree $\frac{\log 2}{\log\lambda}$ where $\lambda$ is irrational number, are indicated. The first example of a group with orbital contracting coefficient (and thus general contracting coefficient) that does not determine the growth of diameters and growth of orbital Shreier graphs is constructed.
Keywords	Shreier graph, iterated monodromy group, sub-hyperbolic polynomial
DOI	doi:10.30970/ms.22.2.159-175
Reference	1. Островский А.~М. Решение уравнений и систем уравнений.-- Москва: Изд. иностр. лит., 1963. -- 219~с. 2. Гантмахер Ф.~Р. Теория матриц.-- Москва: Наука, 1966. -- 576 с. 3. Валеев К.~Г. Расщепление спектра матриц.-- Киев: Вища Школа, 1986. -- 269 с. 4. Гайдуш И.~В. Системы с дискретным временем.-- Минск: Ин-т мат. НАН Беларуси, 2001. 5. Bartholdi L. Counting path in graphs // Enseignement Math.-- 1999.-- V.45.-- P.83--131. 6. Bartholdi L., Ceccherini-Silberstein T.~G. Growth series and random walks on some hyperbolic graphs.-- Preprint, 2001. -- 22 p. 7. Bartholdi L., Grigorchuk R. On the spectrum of Hecke type operators related to some fractal groups. Proc. of the Steklov Institute of Mathematics.-- 2000.-- V.231.-- P.5--45. 8. Bartholdi L., Nekrashevych V. Iterated monodromy groups of quadratic polynomials.-- Preprint, 2003. 9. Gaubert S., Gunawardena J. The Perron-Frobenius theorem for homogeneous, monotone functions.-- Preprint, 2003.-- 20 p. 10. Grigorchuk R., \.Zuk A. On the asymptotic spectrum of random walks on infinite families of graphs. In M.~Picardello and W.~Woess, editors, Proceedings of the Conference ``Random Walks and Discrete Potential Theory'', (Cortona), № 22 in Symposia Mathematica, p. 188--204. Cambridge University Press, 1999. 11. Grigorchuk R., \.Zuk A. The lamplighter group as a group generated by a $2$-state automaton and its spectrum // Geom. Dedicata 87, 1-3 (2001), 209--244. 12. Grigorchuk R., \.Zuk A. The Ihara zeta function of infinite graphs, the KNS spectral measure and integrable maps // Proc. of the Conference "Random walks in Vienne", to appear, 2003.-- 39 p. 13. Kr\"on R. Growth of self-similar graphs.-- Vienna: Preprint ESI 1125, 2002.-- 14 p. 14. Bartholdi L., Grigorchuk R., Nekrashevych V. From fractal groups to fractal sets. In Peter Grabner and Wolfgang Woess, editors, Fractals in Graz 2001. Analysis -- Dynamics -- Geometry -- Stochastics, P.25--118, 2003. 15. Nekrashevych V. Iterated monodromy group.-- Preprint, Geneva University, 2002.-- 31~p. 16. Nekrashevych V. Limit spaces of self-similar group actions.-- Preprint, Geneva University, 2002.-- 33~p. 17. Nekrashevych V. Virtual endomorphism of groups // Algebra and Discrete Mathematics.-- 2002.-- V.1, № 1.-- P. 96--136. 18. Previte J.~P. Graph substitutions // Ergodic Theory Dynam. Systems.-- 1998.-- V.18, № 3.-- P. 661--685. 19. Nekrashevych V., Grigorchuk R., Sushchanskii V.I. Automata, dynamical systems and groups // Proc. of the Steklov Institute of Mathematics.-- 2000.-- V.231.-- P. 128--203. 20. Woess W. Random walks on infinite graphs and groups // Cambridge Tracts in Mathematics, 138.-- Cambridge University Press, 1999.
Pages	159-175
Volume	22
Issue	2
Year	2004
Journal	Matematychni Studii
Full text of paper	pdf
Table of content of issue	html