Substitutions for tilings $\{p,q\}$

Abstract

In this paper we consider tiling $\{p,q\}$ of the Euclidean space and of the hyperbolic space, and its dual graph ${\Gamma }_{q,p}$ from a combinatorial point of view. A substitution ${\sigma }_{q,p}$ on an appropriate finite alphabet is constructed. The homogeneity of graph ${\Gamma }_{q,p}$ and its generation function are the basic tools for the construction. The tree associated with substitution ${\sigma }_{q,p}$ is a spanning tree of graph ${\Gamma }_{q,p}$. Let $u_n$ be the number of tiles of tiling $\{p,q\}$ of generation $n$. The characteristic polynomial of the transition matrix of substitution ${\sigma }_{q,p}$ is a characteristic polynomial of a linear recurrence. The sequence $(u_n{)}_{n\ge 0}$ is a solution of this recurrence. The growth of sequence $(u_n{)}_{n\ge 0}$ is given by the dominant root of the characteristic polynomial.