# Hyperbolic Tessellation and Colorings of Trees

Authors: Dong Han Kim; Seonhee Lim
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

We study colorings of a tree induced from
isometries of the hyperbolic plane given an ideal tessellation. We
show that, for a given tessellation of the hyperbolic plane by
ideal polygons, a coloring can be associated with any element of
Isom(ℍ2), and the element is a commensurator of Γ
if and only if its associated coloring is periodic, generalizing a result of Hedlund and Morse.


---

## Body

## 1. Introduction

LetT be a locally finite tree, VT its vertex set, and ET the set of oriented edges of T. Let 𝒜 be a countable set which will be called the alphabet. Let ϕ be a coloring of T, that is, a map ϕ:VT→𝒜. Let Aut(T) be the automorphism group of T.  A periodic coloring is a coloring which is Γ-invariant for some cocompact subgroup Γ⊂Aut(T).In this paper, we study colorings of regular trees induced from some tessellations of the hyperbolic plane.There is a well-known family of sequences coming from rotations of circle as follows. Consider the tiling of the real lineℝ by unit length intervals {[n,n+1):n∈ℤ} and a map t↦at+b from ℝ to itself. There exists an integer j such that each interval [n,n+1) is partitioned into j or j+1 subintervals of the form {[an+b,a(n+1)+b):n∈ℤ}∩{[n,n+1):n∈ℤ}. Consider the sequence (un)n∈ℕ with un∈𝒜={j,j+1}, which is given by the number of such subintervals of [n,n+1). It is well known that this two-sided sequence un is periodic if only if a is rational [1].As a generalization, we associate a coloringϕg of a k-regular tree (k≥3) for any isometry g of the hyperbolic plane, given a specific hyperbolic tessellation 𝒟 generated by a discrete subgroup Γ of the group of isometries on the hyperbolic plane ℍ2. Suppose that each vertex of elements of 𝒟 lies on the boundary of the hyperbolic plane so that the dual graph of 𝒟 is a tree.For such a tessellation𝒟, we show that the coloring ϕg is periodic if and only if g is a commensurator of Γ in Isom(ℍ2). Recall that an element g∈Isom(ℍ2) is called a commensurator ofΓ if and only if gΓg-1∩Γ is a subgroup of Γ and of gΓg-1 of finite index. Let us denote the group of commensurators of Γ by Comm(Γ). Commensurator subgroup Comm(Γ) plays an important role in the study of rigidity of locally symmetric spaces and more generally in geometric group theory ([2–4]).This is a result analogous to the rotation case in the sense that the group of commensurators ofSL2(ℤ) is a group containing SL2(ℚ) with finite index [5].After showing the main theorem (Theorem3), we show that our construction is an analogue of sequences induced from a rotation of circle only when the multiplicative constant a of t↦at+b is rational.We show that, in the case of an isometry ofℍ2 which is not a commensurator, we obtain colorings of unbounded alphabet, in contrast with the motivating example where irrational rotations correspond to Sturmian sequences, which are in particular sequences with a finite alphabet (see Section 3 for details).We then explain in a heuristic way how to obtain eventually periodic colorings and colorings of “low complexity" by disregarding some information of the induced colorings.


## 2. Periodic Tree Colorings from Hyperbolic Tessellations

We first reformulate the classical example of two-sided sequences mentioned in Section1. Consider the tessellation 𝒟 of the hyperbolic plane (upper-half plane) ℍ2 given by the group Γr generated by the reflections about the lines x=0 and x=1. More precisely, elements of 𝒟 are of the form {z∈ℂ:n≤Re(z)<n+1}. Then Γr=〈z↦-z-,z↦2-z-〉 is isomorphic to the infinite dihedral group, and its dual graph T is a 2-regular tree. Let g=(abcd)∈PSL2(ℝ), which sends z∈ℍ2 to (az+b)/(cz+d). Then it is not difficult to check that g is a commensurator of Γr if and only if c=0, and a/d is rational.For each vertexx∈VT, denote by Dx∈𝒟 the element of 𝒟 dual to x. Let ϕg# be the coloring given by
(1)ϕg#(x)=#{gD:gD∩Dx≠∅,D∈𝒟}.
Then ϕg# is periodic if a/d is rational, c=0, and Sturmian if a/d is irrational, c=0 (e.g., [1], [9, Chapter 6]).Let us generalize the above construction. Let us fix an ideal polygonD in the hyperbolic plane ℍ2. Consider the group Γr generated by the reflections in the edges of D, which is a discrete subgroup of finite covolume in the isometry group of ℍ2. By Poincaré’s theorem on fundamental polygons, there exists a tessellation 𝒟 of ℍ2 by the images of D by the elements of Γr.LetT be the dual graph of the tessellation 𝒟, which is a tree since D is an ideal polygon. The tree T is the Cayley graph of the group Γr.More generally, we will also consider the case whenΓr is generated by the reflections in the edges of a generalized ideal polygon, by which we mean a polygon in ℍ2∪∂ℍ2 such that all vertices are on the boundary ∂ℍ2. Note that such a generalized ideal polygon may have infinite volume.For any giveng∈Isom(ℍ2), we associate a coloring to g as follows. Consider g𝒟={gD:D∈𝒟}. For any vertex x of the dual graph T, the polygon Dx dual to x is a union of subsets of the form Dx∩gD′, for D′∈𝒟, with mutually disjoint interiors. We call by the partition ofDby𝒟∨g𝒟 the collection {D∩gD′:D′∈𝒟} just described (disregarding intersections on the boundary).Definition 1.
Let𝒜 be the set of equivalence classes of partitions of elements of 𝒟, where two partitions of D and D′, respectively, are equivalent if there exists an isometry from D to D′ which sends elements of the partition of D bijectively to elements of the partition of D′. The coloringϕgassociated with g is the map ϕg:VT→𝒜 sending x to the class of the partition of Dx by 𝒟∨g𝒟.LetΓ𝒟⊂Isom(ℍ2) be the set of isometries leaving 𝒟 invariant. Since every D∈𝒟 is a generalized ideal polygon with finitely many sides, Γr is a finite index subgroup of Γ𝒟. Thus g∈Isom(ℍ2) is a commensurator of Γr if and only if g is a commensurator of Γ𝒟.Lemma 2.
For eachx,y∈VT, one has ϕg(x)=ϕg(y) if and only if there exists γ∈Γ𝒟∩gΓ𝒟g-1⊂Isom(ℍ2) such that γDx=Dy, where Dx, Dy are the elements of 𝒟 associated with x,y∈VT.Proof.
Suppose thatγDx=Dy for some γ∈Γ𝒟∩gΓ𝒟g-1. Let the partition of Dx by 𝒟∨g𝒟 be
(2)Dx=⋃i∈I‍(Dx∩gEi),
where {Ei}i∈I⊂𝒟. Then
(3)γDx=⋃i∈I‍(γDx∩γgEi).
Since γ∈Γ𝒟∩gΓ𝒟g-1,  we have γ=gγ′g-1 for some γ′∈Γ𝒟. Thus
(4)γDx=⋃i∈I‍(γDx∩gγ′Ei).
Since gγ′Ei are all elements of g𝒟, the above partition is a partition of γDx by 𝒟∨g𝒟. Therefore, the colorings ϕg on Dx and Dy=γDx are the same.
Conversely, any isometry fromDx to Dy extends to an isometry of ℍ2 leaving 𝒟 invariant. Thus if ϕg(x)=ϕg(y), then there exists γ∈Γ𝒟 such that γDx=Dy which sends elements of the partition of Dx by 𝒟∨g𝒟 bijectively to those of Dy. Let us denote the partitions of Dx and Dy=γDx by 𝒟∨g𝒟 by
(5)Dx=⋃i∈I‍(Dx∩gEi),Dy=γDx=⋃j∈J‍(γDx∩gFj),
for some {Ei}i∈I,{Fj}j∈J⊂𝒟. Since Dx and Dy have the same coloring, the above partition is equal to
(6)γDx=⋃i∈I‍(γDx∩γgEi).
Thus I=J, and by rearranging Fj if necessary, we have Dy∩gFi=Dy∩γgEi for each i. Since 𝒟 is a tessellation by ideal polygons, this implies that gFi=γgEi.  As Fi and Ei are elements of 𝒟, there exists γi∈Γ𝒟 such that Fi=γiEi. Thus gγi(γg)-1 stabilizes Ei; thus it is an element of Γ𝒟, say γ′. We conclude that γ′γ=gγig-1∈gΓ𝒟g-1 satisfies the statement of the lemma.Now let us formulate our theorem.Theorem 3.
LetΓr be a group generated by the reflections in the edges of a generalized ideal polygon. An isometry g∈Isom(ℍ2) is a commensurator of Γr if and only if its associated coloring ϕg is periodic.Proof.
As we mentioned earlier,g∈Comm(Γr) if and only if g∈Comm(Γ𝒟). Suppose that Γ′=gΓ𝒟g-1∩Γ𝒟 is a finite-indexed subgroup of Γ𝒟. By Lemma 2, we know that ϕg is Γ′-invariant. Since Γ𝒟 is cocompact in Aut(T), Γ′ is also a cocompact discrete subgroup of Aut(T). Thus ϕg is periodic.
Conversely, suppose thatϕg is periodic. Let Γ be a cocompact subgroup of Aut(T) preserving ϕg. For any x∈VT and γ∈Γ we have ϕg(x)=ϕg(γx); thus, by Lemma 2, there exists γ′∈Γ′=Γ𝒟∩gΓ𝒟g-1 such that γ′(Dx)=Dγx. Letting Γ′′={γ′∈Γ′:γ∈Γ}, it follows that Γ′′∖T≃Γ′∖T is finite since Γ∖T is finite. Since Γr is a finite index subgroup of Γ𝒟 and T is the Cayley graph of Γr, Γ′⊂Γ𝒟 is of finite index. Therefore g is a commensurator of Γ𝒟, thus a commensurator of Γr.Note that the coloringϕg# on a 2-regular tree in (1) is periodic if ϕg is periodic.Now let us provide some examples of isometries of the hyperbolic plane giving periodic colorings. A periodic coloring which isΓ-invariant for some Γ⊂Isom(ℍ2) will be expressed on the quotient, denoted by Γ∖∖T, which is either a graph (if there is no torsion element) or a graph of groups (if there are some torsion elements, we attach the stabilizers of vertices and edges on the quotient graph). In fact, we will express a coloring on the edge-indexed graph of the quotient graph of groups Γ∖∖T, as we only need the edge-indexed graph of a graph of groups to recover T from a graph of groups.Recall that the edge-indexed graph of a graph of groups is a graph with an index on each oriented edge, where the graph is given by the quotient graphΓ∖T and the index i(e) of the oriented edge e is given by the index of the edge group Ge in the vertex group G∂0(e) of the initial vertex ∂0(e) of e. (For details on graph of groups and the edge-indexed graph of a graph of groups, see [6–8].)Example 4.
Consider the Farey tessellation𝒟 of the hyperbolic plane, which is the tessellation with D the ideal triangle of vertices ∞, 0, and 1. Then Γr=〈-z,z/(2z-1),2-z〉, and the dual graph of Γr is a 3-regular tree T. Note that Γr∩PSL2(ℤ) is a subgroup of Γr of index 2. Γr is commensurable to PSL2(ℤ) as Γr∩PSL2(ℤ) is a subgroup of PSL2(ℤ) of index six since {z,1/(1-z),(z+1)/z} is the stabilizer subgroup of D in PSL2(ℤ).A hyperbolic elementg1:z↦3z and a parabolic element g2:z↦z+(1/2) is considered in Figure 1. The associated colorings ϕg1 and ϕg2 are both periodic.Examples of isometryg associated with periodic colorings.
(a)
z
↦
3
z
(b)
z
↦
z
+
(
1
/
2
)The periodic coloring of the edge-indexed graph of a graph of groupsΓ∖T for z↦3z and z↦z+(1/2) is as follows:
(7)
Here, vertices a and b represent the ideal triangle partitioned as
(8)
respectively. On the other hand,
(9)
In this graph, vertices a and b represent the ideal triangle partitioned as
(10)
respectively (see Figure 1).Remark also that an elliptic elementz↦(2z-1)/(z+1) has a periodic coloring identical to that of z↦3z.


## 3. Eventually Periodic Colorings and Their Generalizations

Now consider an element ofIsom(ℍ2) which is not a commensurator of Γr. We know that the associated coloring ϕg is not periodic.Corollary 5.
Letϕg be a coloring associated with an element g∈Isom(ℍ2) which is not a commensurator of Γr. Then its associated coloring has infinite alphabet.Proof.
LetΓ′=Γ𝒟∩gΓ𝒟g-1 and Γ=Γr∩Γ′. By Lemma 2, ϕg(x)=ϕg(y) implies that x, y are in the same right coset of Γ. Therefore the coloring ϕg has a finite alphabet if and only if Γ is a finite index subgroup of Γr. By Theorem 3, finiteness of the coloring alphabet is equivalent to the fact that g is a commensurator of Γr.This phenomenon is in contrast to the motivating example of circle rotation explained in the beginning of the last section. In that case, irrational rotations correspond to nonperiodic colorings. However they are defined on a finite set of alphabets, and the corresponding sequences are Sturmian, that is, sequences with subword complexityp(n)=n+1. See [9] for Sturmian sequences.Now let us explain how to obtain colorings of “low complexity” with a finite set of alphabets from hyperbolic tessellations by disregarding some information, as the coloring on a 2-regular treeϕg# in (1) for noncommensurable g is Sturmian.Definition 6.
One calls a coloringϕ  eventually periodic if there exists a subtree K of finite number of vertices such that T-K=∪Ti is a finite union of subtrees Ti such that ϕ on each Ti can be extended to a periodic coloring on T.In the next examples, let us denote a geodesic inℍ2 between points x,y∈∂ℍ2 by (x,y), and let us call the edges in ℝ=∂ℍ2 boundary edges.Example 7.
Let𝒟 be the tessellation of ℍ2 with D a generalized ideal polygon whose edges are two geodesics (-2,2), (-1,1) and two boundary edges [-2,-1],  [1,2]. Let en=(-2n,2n). An element of 𝒟 is a generalized ideal polygon which is the region bounded by en,  en+1, for some n∈ℤ, which we denote by Dn. The dual graph is a 2-regular tree T, and we can naturally denote the element of VT dual to Dn by n∈ℤ.
In this case, the commensurator ofΓr is of the form z↦az and z↦a/z for a∈ℝ. If g is considered as a map on ℍ2∪∂ℍ2, then g∈Comm(Γr) if and only if g({0,∞})={0,∞}.
Letg∉Comm(Γr) and ϕg0 be a coloring given by
(11)ϕg0(m)={a,ifthereisD∈𝒟suchthatgD⊂Dm,b,otherwise.
If the boundary edge[2m,2m+1] or [-2m+1,-2m] contains g(0) (or g(∞)) in its interior, then Dm contains gDn∈g𝒟, for sufficiently small (or large, resp.) n. This is the case when all vertices of gDn are contained in one boundary edge of Dm.
Otherwise, we claim that there is noD∈𝒟 such that gD⊂Dm. Indeed, suppose gDn is contained in Dm. The only remaining case is when the two boundary edges of gDn are contained in both of the boundary edges of Dm. Let γ be the element of Γ sending Dm to Dn. Since gγ is an isometry of ℍ2 sending Dm into itself and the boundary edges of g(Dm) are contained in both of the boundary edges of Dm, it sends the geodesic segment ℓ of minimal distance between em, em+1, which is the intersection of the y-axis with Dm, to a geodesic segment of minimal distance between gγem, gγem+1. Thus the distance between gγem, gγem+1 is bounded above by the length of ℓ∩gγDm, which is strictly less than the length of ℓ, which is the distance between em and em+1. This contradicts the fact that gγ is an isometry.
Therefore, all vertices except for one or two are colored byb, and the remaining one or two vertices whose dual generalized ideal polygon contains g(0) or g(∞) in its interior are colored by a. Hence, by omitting one or two vertices, one obtains a periodic coloring. Thus, ϕg0  is an eventually periodic coloring.
In Figure2, an example of g:z↦(z-11)/(10(z+1)) is presented. In this case, there are exactly two vertices colored by a, that is, ϕg0(m)=a for m=-2, 0 and ϕg0(m)=b otherwise.Figure 2
z
↦
(
z
-
11
)
/
(
10
(
z
+
1
)
).Figure 3
z
↦
3
z.Figure 4
z
↦
z
+
17.Now consider the Farey tessellation𝒟 and the corresponding group Γ. The dual graph of Γ is a 3-regular tree T. Let us provide two examples of colorings given by non-commensurable elements of Γ in Isom(ℍ2).Example 8.
Letg:z↦αz with irrational α. Then g∉Comm(Γr). Let ϕg1 be a coloring given by
(12)ϕg1(x)={a,if∃D∈𝒟suchthatDx∩gDcontainsageodesicline,b,otherwise
for x∈VT and Dx∈𝒟 corresponding to x. A geodesic line is contained in Dx∩gD if only if the two ideal triangles Dx and gD have two common vertices. Since the only possible rational vertices of gD are 0 and ∞, ϕg1(x)=a if and only if Dx corresponds to ideal triangle of vertices (0,1,∞) or (-1,0,∞). Therefore, ϕg1  is an eventually periodic coloring, and the coloring of the edge-indexed graph of a graph of groups is as follows:(13)
For example, Figure3 shows the case g:z↦3z.Example 9.
Letg:z↦z+β with irrational β. Then we have g∉Comm(Γr). Let ϕg2  be a coloring given by
(14)ϕg2(x)={a,ifthereisD∈𝒟suchthatDx∩gDisnotcompact,b,otherwise
for x∈VT and Dx∈𝒟 corresponding to x. If Dx∩gD is not compact, then Dx and gD have at least one common vertex. Since all vertices of g𝒟 other than ∞ are irrational, ϕg2(x)=a if and only if Dx has the vertex of ∞, which is the only possible common vertex of Dx with gD∈g𝒟. Therefore, ϕg2  is a coloring with two colors whose coloring of the edge-indexed graph of a graph of groups is as follows:(15)
For example, Figure4 shows the case g:z↦z+17.
We remark that this last example has the number of colored balls up to isometry equal ton+2. We believe that the colorings of this type (i.e., with the number of isometry classes of colored balls being n+2) are the ones corresponding to Sturmian sequences. We leave systematic studies about them for future research.Remark 10.
We can generalize the construction in this paper from torsion-free discrete subgroup to any discrete subgroup with one cusp: in this generality, one should consider the minimal subtree containing vertices not in∂ℍ2, which is again a tree.



---

*Source: 706496-2013-06-04.xml*