Hostname: page-component-8448b6f56d-t5pn6 Total loading time: 0 Render date: 2024-04-18T05:43:30.571Z Has data issue: false hasContentIssue false
  • English
  • Français

Subword complexity and Sturmian colorings of regular trees

Published online by Cambridge University Press:  13 August 2013

DONG HAN KIM  and
SEONHEE LIM
DONG HAN KIM
Affiliation:
Department of Mathematics Education, Dongguk University-Seoul, Seoul 100-715, Korea email kim2010@dongguk.edu
SEONHEE LIM
Affiliation:
Department of Mathematical Sciences, Seoul National University, 1 Gwanak-ro, Gwanak-gu, Seoul, 151-747, Korea email slim@snu.ac.kr
Get access Rights & Permissions [Opens in a new window]

Abstract

In this article, we discuss subword complexity of colorings of regular trees. We characterize colorings of bounded subword complexity and study Sturmian colorings, which are colorings of minimal unbounded subword complexity. We classify Sturmian colorings using their type sets. We show that any Sturmian coloring is a lifting of a coloring on a quotient graph of the tree which is a geodesic or a ray, with loops possibly attached, thus a lifting of an ‘infinite word’. We further give a complete characterization of the quotient graph for eventually periodic colorings.

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 35 , Issue 2 , April 2015 , pp. 461 - 481
Copyright
© Cambridge University Press, 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Avni, N., Lim, S. and Nevo, E.. On commensurator growth. Israel J. Math. 188 (2012), 259–279.Google Scholar
Bass, H.. Covering theory for graphs of groups. J. Pure Appl. Algebra 89 (1–2) (1993), 3–47.Google Scholar
Bass, H. and Kulkarni, R.. Uniform tree lattices. J. Amer. Math. Soc. 3 (4) (1990), 843–902.CrossRefGoogle Scholar
Bass, H. and Lubotzky, A.. Tree Lattices (Progress in Mathematics, 176). Birkhäuser, Boston, 2000.Google Scholar
Bass, H., Otero-Espinar, M., Rockmore, D. and Tresser, C.. Cyclic Renormalization and Automorphism Groups of Rooted Trees (Lecture Notes in Mathematics, 1621). Springer, Berlin, 1996.Google Scholar
Berstel, J., Boasson, L., Carton, O. and Fagnot, I.. A first investigation of Sturmian trees. STACS 2007 (Lecture Notes in Computer Science, 4393). Springer, Berlin, 2007, pp. 73–84.Google Scholar
Berstel, J., Boasson, L., Carton, O. and Fagnot, I.. Sturmian trees. Theory Comput. Syst. 46 (3) (2010), 443–478.Google Scholar
Fogg, N. P.. Substitutions in Dynamics, Arithmetics and Combinatorics (Lecture Notes in Mathematics, 1794). Springer, Berlin, 2002.Google Scholar
Gast, N. and Gaujal, B.. Infinite labeled trees: from rational to Sturmian trees. Theoret. Comput. Sci. 411 (7–9) (2010), 1146–1166.Google Scholar
Hedlund, G. and Morse, M.. Symbolic dynamics II: Sturmian trajectories. Amer. J. Math. 62 (1940), 1–42.Google Scholar
Kim, D. and Lim, S.. Hyperbolic tessallation and colorings of trees. Abstr. Appl. Anal. 2013 (2013), 6 pp. doi:10.1155/2013/706496.Google Scholar
Kubena, A. and Thomas, A.. Density of commensurators for uniform lattices of right-angled buildings. J. Group Theory 15 (5) (2012), 565–611.Google Scholar
Lothaire, M.. Algebraic Combinatorics on Words (Encyclopedia of Mathematics and its Applications, 90). Cambridge University Press, Cambridge, 2002.CrossRefGoogle Scholar
Lubotzky, A., Mozes, S. and Zimmer, R.. Superrigidity for the commensurability group of tree lattices. Comment. Math. Helv. 69 (4) (1994), 523–548.CrossRefGoogle Scholar
Margulis, G.. Discrete Subgroups of Semisimple Lie Groups (Ergebnisse der Mathematik und ihrer Grenzgebiete, 17). Springer, Berlin, 1991.CrossRefGoogle Scholar
Rémy, B.. Topological simplicity, commensurator super-rigidity and non-linearities of Kac–Moody groups. Geom. Funct. Anal. 14 (4) (2004), 810–852.Google Scholar
Serre, J.-P.. Trees. Springer, Berlin–New York, 1980.Google Scholar
Shalom, Y.. Rigidity of commensurators and irreducible lattices. Invent. Math. 141 (1) (2000), 1–54.Google Scholar