4
$\begingroup$

For computing homology of a simplicial complex, there is the well-known reduction algorithm.

How about for fundamental group of simplicial complexes? Is there any (implementable) algorithm to compute it? (By implementable I mean that it can be programmed on a computer and actually compute the fundamental group.)

I am aware of the method of using maximal trees and generators to determine fundamental group, is that implementable as an algorithm? So far I have only learnt working it out on pen and paper, I am unsure if the simplification of the relations of the generators can be made into an algorithm.

Thanks a lot.

$\endgroup$

1 Answer 1

4
$\begingroup$

Depends on what you mean by "computing" and "algorithm". It is undecidable (even for a two-complex) whether the fundamental group is trivial, though computing a presentation is relatively easy.

$\endgroup$
2
  • $\begingroup$ Thanks. Is there a name for the algorithm to compute a presentation? $\endgroup$
    – yoyostein
    Jul 7, 2018 at 15:50
  • 8
    $\begingroup$ Kruskal's algorithm will give you a maximal tree, and after that the presentation just involves listing the remaining edges as generators, and listing the relations that come from the 2-simplices. I don't really see anything interesting going on algorithmically once you've selected a maximal tree. $\endgroup$
    – Dan Ramras
    Jul 7, 2018 at 17:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.