conference paper
Computing all maps into a sphere
published
Martin
Čadek
author
Marek
Krcál
author 33E21118-F248-11E8-B48F-1D18A9856A87
Jiří
Matoušek
author
Francis
Sergeraert
author
Lukáš
Vokřínek
author
Uli
Wagner
author 36690CA2-F248-11E8-B48F-1D18A9856A870000-0002-1494-0568
SODA: Symposium on Discrete Algorithms
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.
SIAM2012
1 - 10
yes
Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. Computing all maps into a sphere. In: SIAM; 2012:1-10.
Čadek, Martin, Marek Krcál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, and Uli Wagner. “Computing All Maps into a Sphere,” 1–10. SIAM, 2012.
Čadek, Martin, et al. <i>Computing All Maps into a Sphere</i>. SIAM, 2012, pp. 1–10.
Čadek, M., Krcál, M., Matoušek, J., Sergeraert, F., Vokřínek, L., & Wagner, U. (2012). Computing all maps into a sphere (pp. 1–10). Presented at the SODA: Symposium on Discrete Algorithms, SIAM.
M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, and U. Wagner, “Computing all maps into a sphere,” presented at the SODA: Symposium on Discrete Algorithms, 2012, pp. 1–10.
Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. 2012. Computing all maps into a sphere. SODA: Symposium on Discrete Algorithms, 1–10.
M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, U. Wagner, in:, SIAM, 2012, pp. 1–10.
24402018-12-11T11:57:40Z2021-01-12T06:57:30Z