8
$\begingroup$

It is well-known that the question whether a given connected simplicial complex (or simplicial set) is simply connected, is algorithmically undecidable as it can model the word problem.

Assuming that $X$ is simply connected, is there an algorithmic way how to contract loops?

One way how this can be formalized is as follows. $X$ can be a simply connected simplicial set (with either finitely many nondegenerate simplices in each dimension, or at least with effective homology...) and $\tilde{GX}$ the Kan model of the loop space, such as described here. The loop contraction would than be a map $c: \tilde{GX}_0\to \tilde{GX}_1$ such that $d_0 c(x)=x$ and $d_1 c(x)=1$. Is there any hope to have a general algorithm for evaluating $c(x)$?

$\endgroup$
  • $\begingroup$ @ThomasRot There should be some obstructions in $\pi_2$ to this. If all loops can be uniformly contracted then presumably all the 2-spheroids (and maybe even higher ones) can be contracted too - after all, a 2-sphere is a circle of loops. $\endgroup$ – მამუკა ჯიბლაძე Sep 11 '16 at 22:11
  • 6
    $\begingroup$ This has been widely studied in 2-complexes associated to finite group presentations (whose 1-skeleta are the Cayley graphs). Keywords: Dehn function, automatic groups, etc. $\endgroup$ – YCor Sep 11 '16 at 22:11
  • 2
    $\begingroup$ @ThomasRot What do you do when there is a local minima for energy? It seems you could only use a gradient flow if you know a lot about the metric you put on $X$. $\endgroup$ – Rbega Sep 12 '16 at 13:58
  • $\begingroup$ @ThomasRot think of a dumbbell. Many loops go to a closed geodesic under the gradient flow of energy. $\endgroup$ – Benoît Kloeckner Sep 13 '16 at 12:57
  • $\begingroup$ @BenoîtKloeckner: thanks, after the comment of Rbega I thought of this example as well. I've deleted my other comments as they are not relevant to the discussion. $\endgroup$ – Thomas Rot Sep 13 '16 at 13:42
8
$\begingroup$

I am assuming that you have a complex with finite 2-dimensional skeleton. There is a silly algorithm for contracting loops which is even linear in the combinatorial length of the loop.

Start with defining the "standard presentation" for $\pi_1(X)$, namely, construct a maximal subtree $T\subset X^1$. Generators of $\pi_1(X)$ are represented by edges in $X^1 -T$ connecting vertices of $X$. Let $g_i, i=1,..,n$ be the corresponding loops in $X^1$ (based at a vertex $o\in T$). Since $X$ is simply-connected, there exist combinatorial maps $e_i: D^2\to X$ with boundary maps $\partial e_i=g_i$: You find these by listing all combinatorial maps $D^2\to X$ and examining them one-by-one. Now, each based combinatorial loop $g$ in $(X^1,o)$ is a product of the generators $g_i$ and their inverses: $$ g= g^{\pm 1}_{i_1}....g^{\pm 1}_{i_k} $$ This is again completely algorithmic since it amounts to reading off the product of the oriented edges in $X^1-T$ as they appear in $g$. Lastly, you read off the maps $e_i$ (and their pre-composition with suitable reflections in $D^2$) according to the word $$ w= g^{\pm 1}_{i_1}....g^{\pm 1}_{i_k}. $$
This gives you a combinatorial map $e: D^2\to X$ with $\partial e$ given by $w$. I will leave you the part dealing with constructing a homotopy between the loops $g$ and $w$ inside of $X^1$ (this essentially amounts to contracting $T$ to $o$ and then cancelling the backtracking in $g$).

$\endgroup$
  • $\begingroup$ Thank you. Can you comment please why is it linear in the length of the loop? I'm not well familiar with combinatorial maps but my feeling is that thee might be quite a lot of them.. $\endgroup$ – Peter Franek Sep 12 '16 at 13:12
  • $\begingroup$ @PeterFranek which part of the answer do you find unclear. If this is the part about the generators $g_i$, then yes, the are infinitely many combinatorial maps but because you need to find only n of them the complexity us constant at this stage (independent of $g$). $\endgroup$ – Moishe Kohan Sep 13 '16 at 2:56
  • $\begingroup$ I see, this makes sense if the space is fixed. I assumed it is a part of the input. $\endgroup$ – Peter Franek Sep 13 '16 at 4:48
  • 1
    $\begingroup$ @studiosus -- The set of simply connected (finite, 2-dimensional) simplicial complexes is recursively enumerable. Your answer provides a semi-algorithm that certifies if a loop is contractible. Applied to a generating set for the fundamental group of the 1-skeleton, this gives a semi-algorithm that certifies if a complex is simply connected. Now apply this to a recursive list of all finite 2-complexes. $\endgroup$ – HJRW Sep 13 '16 at 8:30
  • 3
    $\begingroup$ @PeterFranek, it's clear that the complexity of any such (semi-)algorithm is going to be very large (uncomputable). Otherwise one obtains an algorithmic solution to the triviality problem for groups, which is known to be undecidable. The moral of this is that, if you want an efficient algorithm, you need to use something more about $X$. For instance, does it admit a nice geometry? $\endgroup$ – HJRW Sep 13 '16 at 8:33

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.