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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. Is there a name for the algorithm to compute a presentation? $\endgroup$
    – yoyostein
    Commented 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
    Commented Jul 7, 2018 at 17:30

You must log in to answer this question.

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