Continued fraction algorithm for Sturmian colorings of trees

DOI10.1017/ETDS.2017.127MaRDI QIDQ5227742zbMATH OpenOpenAlexFDO

Authors Dong Han Kim, Seonhee Lim

Publication date 7 August 2019

Published in Ergodic Theory and Dynamical Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.06064

zbMATH Keywords

continued fraction algorithm for Sturmian wordsinduction algorithm for Sturmian colorings

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Abstract: Factor complexity $b_{p}hi(n)$ for a vertex coloring $phi$ of a regular tree is the number of colored $n$-balls up to color-preserving automorphisms. Sturmian colorings are colorings of minimal unbounded factor complexity $b_{p}hi(n)=n+2$. In this article, we prove an induction algorithm for Sturmian colorings using colored balls in a way analogous to induction algorithm of Sturmian words. Furthermore, we characterize Sturmian colorings in terms of the data for the induction algorithm.

Recommendations

• Subword complexity and Sturmian colorings of regular trees
• scientific article; zbMATH DE number 6730060
• A First Investigation of Sturmian Trees
• Colorings of trees with linear, intermediate and exponential subball complexity
• A coloring problem for Sturmian and episturmian words

Cites work

• scientific article; zbMATH DE number 3871492 (Why is no real title available?)
• scientific article; zbMATH DE number 3873585 (Why is no real title available?)
• scientific article; zbMATH DE number 3991618 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• CAT(-1)-spaces, divergence groups and their commensurators
• Hyperbolic tessellation and colorings of trees
• On a conjecture of J. Shallit
• On commensurator growth
• Représentation géométrique de suites de complexité $2n+1$
• Substitutions in dynamics, arithmetics and combinatorics
• Subword complexity and Sturmian colorings of regular trees
• Superrigidity for the commensurability group of tree lattices

Cited in

(3)

• Quasi-Sturmian colorings on regular trees
• Subword complexity and Sturmian colorings of regular trees
• Colorings of trees with linear, intermediate and exponential subball complexity

This page was built for publication: Continued fraction algorithm for Sturmian colorings of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5227742)