I've recently renewed my interest in tilings, and as a result have taken some splashes into Word Processing in Groups (in search of good information on the automatic groups related to hyperbolic tilings) and the amazing The Symmetries of Things. This got me thinking about the question in the title: the isogonal embedding of Cayley graphs of certain groups (the simplest example certainly being $\mathbb{Z}^2$ with the presentation $\{a,b\ |\ ab=ba\}$) as plane tilings implies the polynomial growth of those groups. Contrariwise, while a group like the free group on two generators can't have a 'nice' embedding in the plane because of its exponential growth rate, it can be embedded fairly nicely into the hyperbolic plane (indeed, versions of this sort of embedding form the basis of the various hyperbolic visualization tools; see e.g. http://en.wikipedia.org/wiki/Hyperbolic_tree). So what about the Grigorchuk Group $G$?

To be a bit more concrete: I'm particularly interested in the Cayley graph of $G$ with respect to its 'full' (non-minimal) set of generators $a,b,c,d$. Here are the things I've been able to figure out about it from first principles:

  • Obviously this graph can't be isogonally embedded in any Euclidean space, for the reasons given above: since its growth rate is superpolynomial, there's not enough room for all the different group elements of length $n$ to be $n$ unit 'steps' away from the origin in any isogonal manner.
  • The graph has arbitrarily large 'faces' (that is, minimal cycles) in it, corresponding to the lack of a finite presentation of $G$.
  • I'm fairly certain the graph isn't planar: since the generators $b,c,d$ generate a subgroup of $G$ isomorphic to the Klein 4-group, each vertex of the Cayley graph is part of some embedded $K_4$ (corresponding to some element of the form $wa$ and the associated elements $wab, wac, wad$). In particular, the four elements $e, b, c, d$ form a $K_4$ subgraph, and any independent connection of each of these four elements to some other common element (which I'm reasonably certain must exist) would induce a $K_5$ in the Cayley graph and thus imply non-planarity.
  • OTOH, it seems like it should be possible to 'mod out' the Cayley graph of $G$ by these $K_4$s, creating a reduced graph where vertices of the graph correspond to equivalence classes $\langle wa, wab, wac, wad\rangle$ of elements and the four edges from any vertex correspond to (right) multiplication of the element $wa$ by $a$, $ba$, $ca$, and $da$; this seems like it shouldn't fundamentally change the structure of the graph, just collapse the 'trivial' local structure.

It's this last reduced graph that I'm particularly curious about: is it planar? Better yet, does it have any sort of nice (ideally isogonal) embedding into the hyperbolic plane? And if not, is there at least any interesting (again, ideally isogonal) embedding of the full Cayley graph of $G$ into some (finite-dimensional) hyperbolic space?

  • 1
    $\begingroup$ As far as I know, there isn't a nice way to draw the Cayley graph of Grigorchuk's group. You might want to try asking this question on MathOverflow. $\endgroup$ – Jim Belk Jan 9 '14 at 7:02
  • $\begingroup$ Have you looked at de la Harpe's book Topics in Geometric Group Theory? If I recall correctly, he has a whole section on Grigorchuck's group at the very end. I cannot remember if it talks about Cayley graphs though. $\endgroup$ – user1729 Jan 9 '14 at 10:46
  • $\begingroup$ Ask tiling bot on Twitter: twitter.com/tilingbot?lang=en You might get some sense from that. If so, pls ping me I'd love to see it. On an aside, my interest is the Collatz graph and in the set $\Bbb Z[\frac12]\cap(\frac12,1]$ there's a version of the Collatz graph which would be revealing to see in the hyperbolic plane. $\endgroup$ – samerivertwice Oct 2 '18 at 14:55
  • $\begingroup$ P.S. I mention that because I suspect the Grigorchuk graph and the Collatz graph to be similar-looking. It would be really interesting to discover if they really are. $\endgroup$ – samerivertwice Oct 2 '18 at 19:16
  • $\begingroup$ @user334732 we have made a hyperbolic interactive visualization of the Collatz graph here: roguetemple.com/z/hyper/… But I do not understand why this and TilingBot would be related to the Grigorchuk graph. Collatz graph is acyclic, while the Grigorchuk graph clearly is not. (I have just learned about the Grigorchuk group, possibly I will try to make some visualization later.) $\endgroup$ – Zeno Rogue Apr 17 at 22:32

I do not know about embedding in higher dimensional spaces, but here is a general theorem about dimension 2:

Suppose that $G$ is a finitely-generated group which admits a Cayley graph that has an accumulation-free (i.e., proper) topological embedding in the plane. Then $G$ cannot have intermediate growth.

This is a corollary of Theorem 1.1 here, since groups acting properly discontinuously on planar surfaces are well-understood (see references in the link above) and, in particular, they cannot have intermediate growth. Now, if you have an isogonal embedding in the hyperbolic plane $H^2$, then this embedding is accumulation-free in $H^2$. Applying the inverse of the exponential map for $H^2$ to such an embedding we obtain an accumulation-free embedding in $R^2$.

I am not sure what happens if you allow non-proper embeddings, take a look at the references in the link, maybe you can find further information about this.

One more thing: If you drop the isogonality requirement, then every countable graph will properly embed in 3-dimensional space (hyperbolic or Euclidean does not matter).

Addendum: If a planar Cayley graph does not admit a proper planar embedding, then it is easy to show (see the same link above) that the group has at least 2 ends, i.e., it cannot have intermediate growth as well.


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.