# k-connectedness of simplicial complexes

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?

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.

• What does $\pi$ stand for? – Equi Mar 12 '17 at 21:56
• $\pi_1(\mathcal C,v)$ is the fundamental group, used to define simple connectivity. – Lee Mosher Mar 12 '17 at 22:37
• (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? – Equi Mar 13 '17 at 16:19
• 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. – Lee Mosher Mar 15 '17 at 17:29
• Thanks for the advice! I have created a new question earlier today and would really appreciate your help – Equi Mar 15 '17 at 23:12