What does the Cayley graph of the Grigorchuk group 'look like'?

Question

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?

Answer 1

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.

Answer 2

It's this last reduced graph that I'm particularly curious about: is it planar?

An excellent question! I've been trying to find an answer to it, but haven't so far. To my knowledge, it's open.

Here's what $B_{10}$ in the Cayley graph of Grigorchuk group looks like when the $abcd$ "kites" are collapsed and leaves removed:

Here, $B_{10}$ is the ball of words of length 10 or less around identity, with the standard generating set. Each node represents the $K_4$, and each edge corresponds to $a$.

The graph was laid out with Graphviz (neato engine), as is the next one, for $B_{11}$:

I haven't checked whether the larger graphs are planar, but I'd conjecture that they are.

I also didn't experiment enough with edge lengths; these two embeddings are quasi-isometric due to how layout engine works when unconstrained

Certainly a very interesting question, and I didn't yet give up hope of exploring it deeper some day :)