---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Martin
foaf_name: Čadek, Martin
foaf_surname: Čadek
- foaf_Person:
foaf_givenName: Marek
foaf_name: Marek Krcál
foaf_surname: Krcál
foaf_workInfoHomepage: http://www.librecat.org/personId=33E21118-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Jiří
foaf_name: Matoušek, Jiří
foaf_surname: Matoušek
- foaf_Person:
foaf_givenName: Francis
foaf_name: Sergeraert, Francis
foaf_surname: Sergeraert
- foaf_Person:
foaf_givenName: Lukáš
foaf_name: Vokřínek, Lukáš
foaf_surname: Vokřínek
- foaf_Person:
foaf_givenName: Uli
foaf_name: Uli Wagner
foaf_surname: Wagner
foaf_workInfoHomepage: http://www.librecat.org/personId=36690CA2-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-1494-0568
dct_date: 2012^xs_gYear
dct_publisher: SIAM@
dct_title: Computing all maps into a sphere@
...