3
$\begingroup$

The problem is to embed Cayley graph of free group with $n\geq2$ generators (the same as Bethe lattice with coordination number $2n$) into any model of $\mathbb{H}^2$ (we have no model preference, the only condition is to preserve the metric structure of the graph). Any numerical algorithms like MDS are not suitable. Unfortunately, I can't find any explicit formulas. But my guess is that insofar as embedding is unique, formula must exist. I would be glad if someone help with useful papers or provide any useful reasoning.

UPD Two additions: 1) embedding must be isomorphic, 2) I meant the embedding into $\mathbb{H}^n$ – I guess that for $n>2$ generators Cayley graph cannot be embedded into hyperbolic plane.

Improve this question
$\endgroup$
2
  • $\begingroup$ The embedding is definitely not unique. My answer (below) gives just one possibility. $\endgroup$
    – Sam Nead
    Commented Mar 24, 2022 at 19:38
  • 1
    $\begingroup$ "preserve the metric": you won't get any isometric embedding. Just a tripod in a tree can't be embedded isometrically into $H^2$ (or even $H^n$). Still there are bilipschitz embeddings. $\endgroup$
    – YCor
    Commented Mar 25, 2022 at 6:39

1 Answer 1

Reset to default
7
$\begingroup$

The subgroup $\Gamma < \mathrm{SL}(2, \mathbb{R})$ generated by the matrices $ a = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix} $ and $ b = \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix} $ is free of rank two. It acts on the upper half plane model of $\mathbb{H}^2$ via Mobius transformations. The orbit of $i$ gives the vertices of the Cayley graph; translates that differ by $a$, $b$, $a^{-1}$, or $b^{-1}$ are connected by a geodesic edge. It is an exercise to show that this gives the desired embedding. [Hint: build the Voronoi domain about $i$.]

A few remarks.

  1. As YCor points out, no embedding can be isometric.
  2. There are "quasi-isometric" embeddings of the Cayley graph into $\mathbb{H}^2$, but this one is not, as the generators are parabolic.
  3. By taking finite index subgroups you can obtain equally nice actions of higher rank free groups on the hyperbolic plane.
Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ (And the proof that they generate the free group is probably the canonical example of the Ping-pong lemma. ) $\endgroup$
    – Steven Stadnicki
    Commented Mar 24, 2022 at 19:59
  • 1
    $\begingroup$ Thanks for the answer! I don't see if this embedding is isometric - only the isometric embeddings that are interesting for me. For neighboring vertices, everything seems to be fine here, but are the distances to non-neighbors preserved? This requirement led me to write about the uniqueness of the embedding. $\endgroup$
    – Dmitry Vilensky
    Commented Mar 25, 2022 at 4:47
  • $\begingroup$ The embedding is not isometric, and no such embedding exists. I've added a remark to this effect. $\endgroup$
    – Sam Nead
    Commented Mar 25, 2022 at 18:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .