thesis
Algorithmic aspects of homotopy theory and embeddability
IST Austria Thesis
published
Stephan Y
Zhechev
author 3AA52972-F248-11E8-B48F-1D18A9856A87
Uli
Wagner
supervisor
UlWa
department
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.
https://research-explorer.app.ist.ac.at/download/6681/6771/Stephan_Zhechev_thesis.pdf
application/pdfno
https://research-explorer.app.ist.ac.at/download/6681/6772/Stephan_Zhechev_thesis.tex
application/octet-stream
https://research-explorer.app.ist.ac.at/download/6681/6773/supplementary_material.zip
application/zip
'https://creativecommons.org/licenses/by/4.0/'
IST Austria2019
eng
2663-337X10.15479/AT:ISTA:6681
104
https://research-explorer.app.ist.ac.at/record/6774
Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability, IST Austria, 104p.
Zhechev, Stephan Y. <i>Algorithmic Aspects of Homotopy Theory and Embeddability</i>. IST Austria, 2019. <a href="https://doi.org/10.15479/AT:ISTA:6681">https://doi.org/10.15479/AT:ISTA:6681</a>.
S.Y. Zhechev, Algorithmic Aspects of Homotopy Theory and Embeddability, IST Austria, 2019.
Zhechev, Stephan Y. <i>Algorithmic Aspects of Homotopy Theory and Embeddability</i>. IST Austria, 2019, doi:<a href="https://doi.org/10.15479/AT:ISTA:6681">10.15479/AT:ISTA:6681</a>.
Zhechev SY. <i>Algorithmic Aspects of Homotopy Theory and Embeddability</i>. IST Austria; 2019. doi:<a href="https://doi.org/10.15479/AT:ISTA:6681">10.15479/AT:ISTA:6681</a>
S. Y. Zhechev, <i>Algorithmic aspects of homotopy theory and embeddability</i>. IST Austria, 2019.
Zhechev, S. Y. (2019). <i>Algorithmic aspects of homotopy theory and embeddability</i>. IST Austria. <a href="https://doi.org/10.15479/AT:ISTA:6681">https://doi.org/10.15479/AT:ISTA:6681</a>
66812019-07-26T11:14:34Z2020-01-21T13:21:43Z