1

I'm currently trying to read an interesting paper having to do with embedding graphs in hyperbolic spaces. Namely, "Geographic Routing Using Hyperbolic Space" by Robert Kleinberg. Link: http://user.informatik.uni-goettingen.de/~ychen/NC/geo_routing_hyperbolic_infocom07.pdf

In their paper, the proof of existence of this embedding relies on a tiling of the hyperbolic plane. For the case of a triangular tiling (top of page 5), they describe two transformations $a$ and $b$ by their Mobius transformation coefficients:

$$ a = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}, \quad b = \begin{bmatrix} 0 & 1 \\ -1 & 1 \end{bmatrix} $$

They note that $PSL_2(\mathbb{Z})$ is generated by these two transformations. Then they claim (working in the Poincare disc model):

If $\Delta$ is the ideal triangle with vertices $0,1,i$, then $a$ exchanges $\Delta$ with its complex conjugate $\bar{\Delta}$ and $b$ preserves $\Delta$ while cyclically permuting its vertices. As $g$ ranges over all elements of $PSL_2(\mathbb{Z})$, the ideal triangles $g(\Delta)$ form a tiling of the hyperbolic plane.

First of all, I fail to see how $0,1,i$ is an ideal triangle since $0$ is not an ideal point in the Poincare disc. Secondly, I fail to see how these two transformations can tile the whole space with the transformations $a$ and $b$ given above. But I am probably missing something important. Can anyone point me in the right direction?

EDIT: also, Kleinberg gives the explicit form of $a$ and $b$ in terms of mappings on the Poincare disc: $$a: z \mapsto -z \quad \textrm{and} \quad b: z \mapsto \frac{(1+2i)z+1}{z+(1-2i)}$$

gogurt
  • 2,224

1 Answers1

1

For the first part: it would maybe be more correct to call $\Delta$ a semi-ideal triangle; two of its three vertices are at infinity. On the other hand, the union of $\Delta$ and $\bar{\Delta}$ does form the ideal triangle $\langle1, i, -i\rangle$, and the tiling generated by $a$ and $b$ induces a tiling of these ideal triangles, the uniform $\{\infty, 3\}$ tiling.

As far as the second part goes: note that just because $b$ leaves $\Delta$ invariant doesn't mean that $b$ is the identity; in particular, given that $a$ is the reflection about the $(0, 1)$ edge of the triangle, then the conjugates of $a$ by $b$ and $b^{-1}$ — that is, $a^b = b^{-1}ab$ and $a^{b^{-1}} = bab^{-1}$ — are the reflections about the $(0, i)$ and $(1, i)$ edges of the triangle. Now, $a$, $a^b$, and $a^{b^{-1}}$ generate the tiling in the usual Coxeter fashion. (Note that only the induced version of this tiling on $\Delta\cup\bar{\Delta}$ I mentioned above is uniform; the tiling by isomorphs of $\Delta=\langle 0, 1, i\rangle$ is only Catalan, with vertices of valence $4$ and $\infty$).

Steven Stadnicki
  • 51,746
  • Thanks for your very helpful comments! I edited my original post above to add some explicit forms for $a$ and $b$ that Kleinberg had in the paper. My main point of confusion was the ideal triangle aspect. Am I correct in saying that he (more or less) should've been speaking of the ideal triangle $\Delta = (-1, 1, i)$ instead of the semi-ideal triangle $(0,1,i)$? Given his expression for $b$, it doesn't seem like $b$ permutes the vertices of $\Delta$ unless $\Delta$ is given in this way. – gogurt Mar 21 '14 at 20:30