3
$\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$
3
$\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 '18 at 15:50
  • 7
    $\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 '18 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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