Computing all maps into a sphere Journal Article


Author(s): Čadek, Martin; Krčál, Marek; Matoušek, Jiří; Sergeraert, Francis; Vokřínek L; Wagner, Uli
Article Title: Computing all maps into a sphere
Affiliation IST Austria
Abstract: Given topological spaces X,Y, a fundamental problem of algebraic topology is understanding the structure of all continuous maps X→ Y. We consider a computational version, where X,Y are given as finite simplicial complexes, and the goal is to compute [X,Y], that is, all homotopy classes of suchmaps.We solve this problem in the stable range, where for some d ≥ 2, we have dim X ≤ 2d-2 and Y is (d-1)-connected; in particular, Y can be the d-dimensional sphere Sd. The algorithm combines classical tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and simplicial sets) with algorithmic tools from effective algebraic topology (locally effective simplicial sets and objects with effective homology). In contrast, [X,Y] is known to be uncomputable for general X,Y, since for X = S1 it includes a well known undecidable problem: testing triviality of the fundamental group of Y. In follow-up papers, the algorithm is shown to run in polynomial time for d fixed, and extended to other problems, such as the extension problem, where we are given a subspace A ⊂ X and a map A→ Y and ask whether it extends to a map X → Y, or computing the Z2-index-everything in the stable range. Outside the stable range, the extension problem is undecidable.
Keywords: Computational topology; Homotopy groups; Postnikov systems
Journal Title: Journal of the ACM
Volume: 61
Issue 3
ISSN: 0004-5411
Publisher: ACM  
Date Published: 2014-05-01
Start Page: Article number: a17
URL:
DOI: 10.1145/2597629
Notes: The research by M. C. and L. V. was supported by a Czech Ministry of Education grant (MSM 0021622409). The research by M. K. was supported by project GAUK 49209. The research by J. M. and M. K. was also supported by project 1M0545 by the Ministry of Education of the Czech Republic and by Center of Excellence { Inst. for Theor. Comput. Sci., Prague (project P202/12/G061 of GACR). The research by J. M. was also supported by the ERC Advanced Grant No. 267165. The research by U. W. was supported by the Swiss National Science Foundation (SNF Projects 200021-125309, 200020-138230, and PP00P2-138948).
Open access: yes (repository)
IST Austria Authors
  1. Uli Wagner
    45 Wagner
Related IST Austria Work