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)}$$


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$).

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – gogurt Mar 21 '14 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.