Volume 19, issue 4 (2019)

Download this article
Download this article For screen
For printing
Recent Issues

Volume 24
Issue 2, 595–1223
Issue 1, 1–594

Volume 23, 9 issues

Volume 22, 8 issues

Volume 21, 7 issues

Volume 20, 7 issues

Volume 19, 7 issues

Volume 18, 7 issues

Volume 17, 6 issues

Volume 16, 6 issues

Volume 15, 6 issues

Volume 14, 6 issues

Volume 13, 6 issues

Volume 12, 4 issues

Volume 11, 5 issues

Volume 10, 4 issues

Volume 9, 4 issues

Volume 8, 4 issues

Volume 7, 4 issues

Volume 6, 5 issues

Volume 5, 4 issues

Volume 4, 2 issues

Volume 3, 2 issues

Volume 2, 2 issues

Volume 1, 2 issues

The Journal
About the Journal
Editorial Board
Editorial Interests
Submission Guidelines
Submission Page
Policies for Authors
Ethics Statement
ISSN (electronic): 1472-2739
ISSN (print): 1472-2747
Author Index
To Appear
Other MSP Journals
Bredon cohomology and robot motion planning

Michael Farber, Mark Grant, Gregory Lupton and John Oprea

Algebraic & Geometric Topology 19 (2019) 2023–2059

We study the topological invariant TC(X) reflecting the complexity of algorithms for autonomous robot motion. Here, X stands for the configuration space of a system and TC(X) is, roughly, the minimal number of continuous rules which are needed to construct a motion planning algorithm in X. We focus on the case when the space X is aspherical; then the number TC(X) depends only on the fundamental group π = π1(X) and we denote it by TC(π). We prove that TC(π) can be characterised as the smallest integer k such that the canonical π×π–equivariant map of classifying spaces

E(π × π) ED(π × π)

can be equivariantly deformed into the k–dimensional skeleton of ED(π × π). The symbol E(π × π) denotes the classifying space for free actions and ED(π × π) denotes the classifying space for actions with isotropy in the family D of subgroups of π × π which are conjugate to the diagonal subgroup. Using this result we show how one can estimate TC(π) in terms of the equivariant Bredon cohomology theory. We prove that TC(π) max{3,cdD(π × π)}, where cdD(π × π) denotes the cohomological dimension of π × π with respect to the family of subgroups D. We also introduce a Bredon cohomology refinement of the canonical class and prove its universality. Finally we show that for a large class of principal groups (which includes all torsion-free hyperbolic groups as well as all torsion-free nilpotent groups) the essential cohomology classes in the sense of Farber and Mescher (2017) are exactly the classes having Bredon cohomology extensions with respect to the family D.

topological complexity, aspherical spaces, Bredon cohomology
Mathematical Subject Classification 2010
Primary: 55M10
Secondary: 55M99
Received: 16 May 2018
Revised: 29 December 2018
Accepted: 15 January 2019
Published: 16 August 2019
Michael Farber
School of Mathematical Sciences
Queen Mary, University of London
United Kingdom
Mark Grant
Institute of Pure and Applied Mathematics
University of Aberdeen
United Kingdom
Gregory Lupton
Department of Mathematics
Cleveland State University
Cleveland, OH
United States
John Oprea
Department of Mathematics
Cleveland State University
Cleveland, OH
United States