1
$\begingroup$

Let $\mathcal{C}$ be a finite simplicial complex. Is there an algorithm, that can tell wether $\mathcal{C}$ is simply connected? If not, are there restrictions to $\mathcal{C}$ under which such an algorithm exists?

$\endgroup$
4
$\begingroup$

No, there is no such algorithm. Here's why.

Given a finite simplicial complex $\mathcal{C}$ and a choice of vertex $v$, there is an algorithm to write down a finite presentation of $\pi_1(\mathcal{C},v)$. Conversely, given a finite group presentation $\langle g_i \,|\, r_j\rangle$ there is an algorithm to construct a finite simplicial complex $\mathcal{C}$ and vertex $v$ such that $\pi_1(\mathcal{C},v)$ has the given presentation.

Thus, an algorithm as you have asked for exists if and only if an algorithm exists to decide whether, given a group presentation, the group is trivial.

But no such algorithm exists: https://berstein2015.wordpress.com/2015/02/17/just-about-any-property-of-finitely-presented-groups-is-undecidable/

Roughly speaking, the reason no such algorithm exists is that you can algorithmically encode the halting problem for Turing machines into the problem for deciding whether a group presentation presents the trivial group. Hence, if you could decide the latter problem, then you could decide the former, which cannot be done.

$\endgroup$
  • $\begingroup$ What does $\pi$ stand for? $\endgroup$ – Equi Mar 12 '17 at 21:56
  • 1
    $\begingroup$ $\pi_1(\mathcal C,v)$ is the fundamental group, used to define simple connectivity. $\endgroup$ – Lee Mosher Mar 12 '17 at 22:37
  • $\begingroup$ (as a follow up question:) is it possible to algorithmically decide if the neighborhood complex (as defined here) is simply connected? I could't figure out where the critical part of your argument is that would work/fail. Wouldn't it be possible to use graph algorithms to show that the underlying topological space of the neighborhood complex is homeomorphic to a tree and therefore 1-connected? $\endgroup$ – Equi Mar 13 '17 at 16:19
  • $\begingroup$ Generally speaking, followup questions embedded as comments to answers are not a great idea on math.stackexchange, because no-one sees them except the answerer. If you want to pursue that followup, I suggest you post it as a new question. $\endgroup$ – Lee Mosher Mar 15 '17 at 17:29
  • $\begingroup$ Thanks for the advice! I have created a new question earlier today and would really appreciate your help $\endgroup$ – Equi Mar 15 '17 at 23:12

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.