5
$\begingroup$

I'm working through "Groups, Graphs and Trees" by John Meier.

In Chapter 5, he states that in a Cayley Graph, $\Gamma$ (or indeed any graph), the ball of radius n centred at the vertex v, $\mathcal{B}(v,n)$, is the subgraph formed as the union of all paths in $\Gamma$ of length $\le n$ that start at the vertex $v$.

It is then stated that a Cayley graph Γ is constructible if given $n \in N$ one can construct $\mathcal{B}(e,n)$ in a finite amount of time.

My question is what is an example of a non-constructible graph?

In particular, it is implied that there are finitely generated groups which have non-constructible Cayley graphs. I cannot comprehend what such a group looks like.

$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

To construct the Cayley graph you need to be able to solve the word problem in the group, so any group with unsolvable word problem is an example.

In fact the converse is also true - if the group has solvable word problem then you can construct the Cayley graph.

$\endgroup$
3
  • $\begingroup$ Would you be able to go into a specific example of such a group? I had seen the result you quoted in Meier but I am struggling to see what such groups are. $\endgroup$
    – Jalog_the_Martian
    Apr 22, 2022 at 14:16
  • 1
    $\begingroup$ Such groups are complicated (and in some sense artificial), and constructed from Turing machines with unsolvable word problem using HNN extensions. If you really want to learn about them, I would recommend the final two chapters of Rotman's book "An Introduction to the Theory of Groups", $\endgroup$
    – Derek Holt
    Apr 22, 2022 at 16:01
  • $\begingroup$ Okay, thanks. I think that intuitively had concluded these groups must be "artificial". I shall have a look at Rotman. $\endgroup$
    – Jalog_the_Martian
    Apr 22, 2022 at 17:10

You must log in to answer this question.

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