# Algorithmic aspects of homotopy theory and embeddability

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

Download

*Thesis*|

*PhD*|

*Published*|

*English*

Author

Supervisor

Corresponding author has ISTA affiliation

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:6681Zhechev, 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, 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)**

File Name

Stephan_Zhechev_thesis.pdf
1.46 MB

Access Level

Open Access

Date Uploaded

2019-08-07

MD5 Checksum

3231e7cbfca3b5687366f84f0a57a0c0

**Source File**

File Name

Stephan_Zhechev_thesis.tex
303.99 KB

Access Level

Closed Access

Date Uploaded

2019-08-07

MD5 Checksum

85d65eb27b4377a9e332ee37a70f08b6

**Supplementary Material**

File Name

supplementary_material.zip
1.09 MB

Access Level

Closed Access

Date Uploaded

2019-08-07

MD5 Checksum

86b374d264ca2dd53e712728e253ee75

**Material in ISTA:**

**Part of this Dissertation**