Algorithmic aspects of homotopy theory and embeddability

Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria.

Download
OA Stephan_Zhechev_thesis.pdf 1.46 MB [Published Version]

Thesis | PhD | Published | English
Supervisor
Department
Series Title
ISTA Thesis
Abstract
The first part of the thesis considers the computational aspects of the homotopy groups πd(X) of a topological space X. It is well known that there is no algorithm to decide whether the fundamental group π1(X) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute the higher homotopy group πd(X) for any given d ≥ 2. However, these algorithms come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(X). We present an algorithm that, given a simply connected space X, computes πd(X) and represents its elements as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2, we construct a family of simply connected spaces X such that for any simplicial map representing a generator of πd(X), the size of the triangulation of S d on which the map is defined, is exponential in size(X). In the second part of the thesis, we prove that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋, k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable range: Given a finite simplicial complex K of dimension k, decide whether there exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space.
Publishing Year
Date Published
2019-08-08
Publisher
Institute of Science and Technology Austria
Page
104
ISSN
IST-REx-ID

Cite this

Zhechev SY. Algorithmic aspects of homotopy theory and embeddability. 2019. doi:10.15479/AT:ISTA:6681
Zhechev, S. Y. (2019). Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:6681
Zhechev, Stephan Y. “Algorithmic Aspects of Homotopy Theory and Embeddability.” Institute of Science and Technology Austria, 2019. https://doi.org/10.15479/AT:ISTA:6681.
S. Y. Zhechev, “Algorithmic aspects of homotopy theory and embeddability,” Institute of Science and Technology Austria, 2019.
Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria.
Zhechev, Stephan Y. Algorithmic Aspects of Homotopy Theory and Embeddability. Institute of Science and Technology Austria, 2019, doi:10.15479/AT:ISTA:6681.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
Access Level
OA Open Access
Date Uploaded
2019-08-07
MD5 Checksum
3231e7cbfca3b5687366f84f0a57a0c0

Source File
File Name
Access Level
Restricted Closed Access
Date Uploaded
2019-08-07
MD5 Checksum
85d65eb27b4377a9e332ee37a70f08b6
Supplementary Material
Access Level
Restricted Closed Access
Date Uploaded
2019-08-07
MD5 Checksum
86b374d264ca2dd53e712728e253ee75

Material in ISTA:
Part of this Dissertation

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar