Topological complexity

Rummaging in the arXiv I ran across this article and the notion of topological complexity which is really appealing. The idea of topological complexity isn’t quite new, it was developed by M. Farber in a short article published in 2003 in Discrete & Computational Geometry. The article doesn’t even have a proper review on MathSciNet, nevertheless the idea took off quickly and the paper (as of today) has 136 listed citations. (It is definitely a considerable piece of ignorance from my side that I’ve never heard of it before.)

So what is topological complexity? To explain this I will paraphrase the motivation given in Farbers original paper. Let \(X\) be the state space of a mechanical system. Assume that \(X\) is path-connected. In order to plan motions of the system one needs a method to exhibit for every pair of states \((A,B) \in X \times X\) a continuous path connecting \(A\) and \(B\). Let \(PX\) be the space of continuous paths \([0,1] \to X\) and let \(\pi \colon PX \to X \times X\) denote the maps with maps a path to its start and endpoint. A great solution to the motion planning problem would be to come up with a continuous section \[ s \colon X \times X \to PX \] to the function \(\pi\colon PX \to X \times X\). However, such a section exists if and only if \(X\) is contractible. Indeed, one can use a contraction to move every state to one fixed state.

From a algorithmic point of view it is sufficient to ask for a weaker form of solution: Write \(X\times X\) as finite union of open sets \[ X\times X = U_1 \cup U_2 \cup U_3 \cup …\cup U_k\] and find a section \(s_i \colon U_i \to PX \) to \(\pi\) on each of these sets. Given a pair \((A,B)\) one can take the first \(U_i\) which contains the pair \((A,B)\) and use \(s_i(A,B)\) to move state \(A\) to state \(B\). Et voilá, this is the notion of topological complexity:

Definition: The topological complexity \(TC(X)\) of a path-connected topological space \(X\) is the smallest number \(k\) such that \(X \times X\) admits an open cover \[ X \times X = U_1 \cup U_2 \cup U_3 \cup …\cup U_k \] consisting of \(k\) sets such that there is a continuous section \(s_i \colon U_i \to PX\) to \(\pi\colon PX \to X \times X\) on each set \(U_i\).

Farber in particular notes that the topological complexity is a homotopy invariant and that \(TC(X) \leq 2\dim(X)+1\) if \(X\) is (for instance) a finite dimensional CW-complex. In fact, this bound is sharp, for instace, the topological complexity of the Klein bottle is 5; see this article (warning: they normalize topological complexity differently).

There is a considerable amount of results on topological complexity in the literature. Let me mention two that are related to the fundemental group of the topological space. (1) The arxiv preprint which made me fall into this rabit hole studies closed connected manifolds \(X\) with abelian fundamental group such that \(TC(X) < 2\dim(X) +1 \). In particular every non-orientable closed manifold with abelian \(\pi_1\) has this property. (2) A result of Farber and Mescher states that the topological complexity \(TC(X)\) of an aspherical finite CW-complex \(X\) with hyperbolic fundamental group \(\Gamma\) either equals the cohomological dimension \(c\) of \(\Gamma \times \Gamma\) or equals \(c+1\).

Leave a Reply

Your email address will not be published. Required fields are marked *