Computing all maps into a sphere Conference Paper


Author(s): Čadek, Martin; Krčál, Marek; Matoušek, Jiří; Sergeraert, Francis; Vokřínek, Lukáš; Wagner, Uli
Title: Computing all maps into a sphere
Affiliation
Abstract: We present an algorithm for computing [X, Y], i.e., all homotopy classes of continuous maps X → Y, where X, Y are topological spaces given as finite simplicial complexes, Y is (d - 1)-connected for some d ≥ 2 (for example, Y can be the d-dimensional sphere S d), and dim X ≤ 2d - 2. These conditions on X, Y guarantee that [X, Y] has a natural structure of a finitely generated Abelian group, and the algorithm finds generators and relations for it. We combine several tools and ideas from homotopy theory (such as Postnikov systems, simplicial sets, and obstruction theory) with algorithmic tools from effective algebraic topology (objects with effective homology). We hope that a further extension of the methods developed here will yield an algorithm for computing, in some cases of interest, the ℤ 2-index, which is a quantity playing a prominent role in Borsuk-Ulam style applications of topology in combinatorics and geometry, e.g., in topological lower bounds for the chromatic number of a graph. In a certain range of dimensions, deciding the embeddability of a simplicial complex into ℝ d also amounts to a ℤ 2-index computation. This is the main motivation of our work. We believe that investigating the computational complexity of questions in homotopy theory and similar areas presents a fascinating research area, and we hope that our work may help bridge the cultural gap between algebraic topology and theoretical computer science.
Keywords: topological spaces; Algebraic topology; Lower bounds; Simplicial complex; Homotopy theory; Abelian group; Algorithmic tools; Chromatic number; Combinatorics; Continuous map; Generators and relations; Homotopies; Index computation; Natural structures; Theoretical computer science
Conference Title: SODA: Symposium on Discrete Algorithms
Conference Dates: January 17-19, 2012
Conference Location: Kyoto, Japan
ISBN: 1557-9468
Publisher: SIAM  
Date Published: 2012-01-01
Start Page: 1
End Page: 10
URL:
Open access: no
IST Austria Authors
  1. Uli Wagner
    50 Wagner
  2. Marek Krčál
    10 Krčál
Related IST Austria Work