3
$\begingroup$

Let $X= X(P)$ be the Cayley complex of a finite group presentation $P=<S | R>$. Are there geometric properties of $X$ that are known to be decidable by an algorithm that takes $P$ as input? For example, being a tree is trivially decidable. I think I can prove that being planar is also decidable.

The question makes more sense for properties that depend on the choice of $P$ and not only on the group, so that e.g. the Adjan-Rabin theorem cannot be applied.

$\endgroup$
5
  • 1
    $\begingroup$ The list of possible 'geometric properties' is so long that this question might go on forever. But it's certainly the case that you can decide a lot of things by looking at the link $L(P)$ of the unique vertex of the presentation complex of $P$. For instance, $X(P)$ should be planar (ie embeddable in $S^2$) if and only if the cone on $L(P)$ is planar. $\endgroup$
    – HJRW
    Mar 25, 2015 at 11:56
  • 1
    $\begingroup$ You have to say clearly what you call "Cayley complex"; I assume it includes multiple edges in case some generators are equal in the group, and self-loops in case some generators are trivial in the group. For instance, the Cayley complex of the presentation $\langle x\mid x\rangle$ of the trivial group should be one vertex, with a self-loop and a 1-gon filling this self-loop. $\endgroup$
    – YCor
    Mar 25, 2015 at 14:19
  • $\begingroup$ I agree with @YCor; you need to say what you mean by the Cayley complex. If this is just the canonical complex which comes from the finite presentation P, then you might as well just say that your input is P. If, on the other hand, some "reductions" have been done, then you need to mention what. If your property does not depend on P, then you will run in to just about every undecidable property of finitely presented groups. $\endgroup$
    – MCC
    Mar 26, 2015 at 13:19
  • $\begingroup$ @HJRW: I reformulated the question; what I meant to ask was rather if there had been any work on proving that this and that property of a Cayley complex is decideable. $\endgroup$
    – Agelos
    Mar 26, 2015 at 13:55
  • $\begingroup$ @YCor: Your guesses are correct: it includes multiple edges in case some generators are equal in the group, and self-loops in case some generators are trivial in the group. $\endgroup$
    – Agelos
    Mar 26, 2015 at 13:58

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.