Continued fraction algorithm for Sturmian colorings of trees

DOI10.1017/ETDS.2017.127zbMATH Open1426.05045arXiv1609.06064OpenAlexW2522311665MaRDI QIDQ5227742FDOQ5227742

Authors: Dong Han Kim, Seonhee Lim 

Publication date: 7 August 2019

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Représentation géométrique de suites de complexité $2n+1$
• Substitutions in dynamics, arithmetics and combinatorics
• CAT(-1)-spaces, divergence groups and their commensurators
• Title not available (Why is that?)
• Title not available (Why is that?)
• Superrigidity for the commensurability group of tree lattices
• On a conjecture of J. Shallit
• Subword complexity and Sturmian colorings of regular trees
• On commensurator growth
• Hyperbolic tessellation and colorings of trees

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)