---
_id: '6774'
abstract:
- lang: eng
text: "A central problem of algebraic topology is to understand the homotopy groups
\ \U0001D70B\U0001D451(\U0001D44B) of a topological space X. For the computational
version of the problem, it is well known that there is no algorithm to decide
whether the fundamental group \U0001D70B1(\U0001D44B) 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 \U0001D70B1(\U0001D44B)
\ trivial), compute the higher homotopy group \U0001D70B\U0001D451(\U0001D44B)
\ for any given \U0001D451≥2 . However, these algorithms come with a caveat:
They compute the isomorphism type of \U0001D70B\U0001D451(\U0001D44B) , \U0001D451≥2
\ as an abstract finitely generated abelian group given by generators and relations,
but they work with very implicit representations of the elements of \U0001D70B\U0001D451(\U0001D44B)
. Converting elements of this abstract group into explicit geometric maps from
the d-dimensional sphere \U0001D446\U0001D451 to X has been one of the main
unsolved problems in the emerging field of computational homotopy theory. Here
we present an algorithm that, given a simply connected space X, computes \U0001D70B\U0001D451(\U0001D44B)
\ and represents its elements as simplicial maps from a suitable triangulation
of the d-sphere \U0001D446\U0001D451 to X. For fixed d, the algorithm runs
in time exponential in size(\U0001D44B) , the number of simplices of X. Moreover,
we prove that this is optimal: For every fixed \U0001D451≥2 , we construct a
family of simply connected spaces X such that for any simplicial map representing
a generator of \U0001D70B\U0001D451(\U0001D44B) , the size of the triangulation
of \U0001D446\U0001D451 on which the map is defined, is exponential in size(\U0001D44B)
."
article_type: original
author:
- first_name: Marek
full_name: Filakovský, Marek
id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
last_name: Filakovský
- first_name: Peter
full_name: Franek, Peter
id: 473294AE-F248-11E8-B48F-1D18A9856A87
last_name: Franek
orcid: 0000-0001-8878-8397
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Stephan Y
full_name: Zhechev, Stephan Y
id: 3AA52972-F248-11E8-B48F-1D18A9856A87
last_name: Zhechev
citation:
ama: Filakovský M, Franek P, Wagner U, Zhechev SY. Computing simplicial representatives
of homotopy group elements. Journal of Applied and Computational Topology.
2018;2(3-4):177-231. doi:10.1007/s41468-018-0021-5
apa: Filakovský, M., Franek, P., Wagner, U., & Zhechev, S. Y. (2018). Computing
simplicial representatives of homotopy group elements. Journal of Applied and
Computational Topology. Springer. https://doi.org/10.1007/s41468-018-0021-5
chicago: Filakovský, Marek, Peter Franek, Uli Wagner, and Stephan Y Zhechev. “Computing
Simplicial Representatives of Homotopy Group Elements.” Journal of Applied
and Computational Topology. Springer, 2018. https://doi.org/10.1007/s41468-018-0021-5.
ieee: M. Filakovský, P. Franek, U. Wagner, and S. Y. Zhechev, “Computing simplicial
representatives of homotopy group elements,” Journal of Applied and Computational
Topology, vol. 2, no. 3–4. Springer, pp. 177–231, 2018.
ista: Filakovský M, Franek P, Wagner U, Zhechev SY. 2018. Computing simplicial representatives
of homotopy group elements. Journal of Applied and Computational Topology. 2(3–4),
177–231.
mla: Filakovský, Marek, et al. “Computing Simplicial Representatives of Homotopy
Group Elements.” Journal of Applied and Computational Topology, vol. 2,
no. 3–4, Springer, 2018, pp. 177–231, doi:10.1007/s41468-018-0021-5.
short: M. Filakovský, P. Franek, U. Wagner, S.Y. Zhechev, Journal of Applied and
Computational Topology 2 (2018) 177–231.
date_created: 2019-08-08T06:47:40Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2023-09-07T13:10:36Z
day: '01'
ddc:
- '514'
department:
- _id: UlWa
doi: 10.1007/s41468-018-0021-5
file:
- access_level: open_access
checksum: cf9e7fcd2a113dd4828774fc75cdb7e8
content_type: application/pdf
creator: dernst
date_created: 2019-08-08T06:55:21Z
date_updated: 2020-07-14T12:47:40Z
file_id: '6775'
file_name: 2018_JourAppliedComputTopology_Filakovsky.pdf
file_size: 1056278
relation: main_file
file_date_updated: 2020-07-14T12:47:40Z
has_accepted_license: '1'
intvolume: ' 2'
issue: 3-4
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 177-231
project:
- _id: 25F8B9BC-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M01980
name: Robust invariants of Nonlinear Systems
- _id: 3AC91DDA-15DF-11EA-824D-93A3E7B544D1
call_identifier: FWF
name: FWF Open Access Fund
publication: Journal of Applied and Computational Topology
publication_identifier:
eissn:
- 2367-1734
issn:
- 2367-1726
publication_status: published
publisher: Springer
quality_controlled: '1'
related_material:
record:
- id: '6681'
relation: dissertation_contains
status: public
status: public
title: Computing simplicial representatives of homotopy group elements
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2
year: '2018'
...
---
_id: '1408'
abstract:
- lang: eng
text: 'The concept of well group in a special but important case captures homological
properties of the zero set of a continuous map (Formula presented.) on a compact
space K that are invariant with respect to perturbations of f. The perturbations
are arbitrary continuous maps within (Formula presented.) distance r from f for
a given (Formula presented.). The main drawback of the approach is that the computability
of well groups was shown only when (Formula presented.) or (Formula presented.).
Our contribution to the theory of well groups is twofold: on the one hand we improve
on the computability issue, but on the other hand we present a range of examples
where the well groups are incomplete invariants, that is, fail to capture certain
important robust properties of the zero set. For the first part, we identify a
computable subgroup of the well group that is obtained by cap product with the
pullback of the orientation of (Formula presented.) by f. In other words, well
groups can be algorithmically approximated from below. When f is smooth and (Formula
presented.), our approximation of the (Formula presented.)th well group is exact.
For the second part, we find examples of maps (Formula presented.) with all well
groups isomorphic but whose perturbations have different zero sets. We discuss
on a possible replacement of the well groups of vector valued maps by an invariant
of a better descriptive power and computability status.'
acknowledgement: 'Open access funding provided by Institute of Science and Technology
(IST Austria). '
article_processing_charge: Yes (via OA deal)
author:
- first_name: Peter
full_name: Franek, Peter
id: 473294AE-F248-11E8-B48F-1D18A9856A87
last_name: Franek
- first_name: Marek
full_name: Krcál, Marek
id: 33E21118-F248-11E8-B48F-1D18A9856A87
last_name: Krcál
citation:
ama: Franek P, Krcál M. On computability and triviality of well groups. Discrete
& Computational Geometry. 2016;56(1):126-164. doi:10.1007/s00454-016-9794-2
apa: Franek, P., & Krcál, M. (2016). On computability and triviality of well
groups. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-016-9794-2
chicago: Franek, Peter, and Marek Krcál. “On Computability and Triviality of Well
Groups.” Discrete & Computational Geometry. Springer, 2016. https://doi.org/10.1007/s00454-016-9794-2.
ieee: P. Franek and M. Krcál, “On computability and triviality of well groups,”
Discrete & Computational Geometry, vol. 56, no. 1. Springer, pp. 126–164,
2016.
ista: Franek P, Krcál M. 2016. On computability and triviality of well groups. Discrete
& Computational Geometry. 56(1), 126–164.
mla: Franek, Peter, and Marek Krcál. “On Computability and Triviality of Well Groups.”
Discrete & Computational Geometry, vol. 56, no. 1, Springer, 2016,
pp. 126–64, doi:10.1007/s00454-016-9794-2.
short: P. Franek, M. Krcál, Discrete & Computational Geometry 56 (2016) 126–164.
date_created: 2018-12-11T11:51:51Z
date_published: 2016-07-01T00:00:00Z
date_updated: 2023-02-23T10:02:11Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1007/s00454-016-9794-2
ec_funded: 1
file:
- access_level: open_access
checksum: e0da023abf6b72abd8c6a8c76740d53c
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:55Z
date_updated: 2020-07-14T12:44:53Z
file_id: '4846'
file_name: IST-2016-614-v1+1_s00454-016-9794-2.pdf
file_size: 905303
relation: main_file
file_date_updated: 2020-07-14T12:44:53Z
has_accepted_license: '1'
intvolume: ' 56'
issue: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 126 - 164
project:
- _id: 25F8B9BC-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M01980
name: Robust invariants of Nonlinear Systems
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '5799'
pubrep_id: '614'
quality_controlled: '1'
related_material:
record:
- id: '1510'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: On computability and triviality of well groups
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 56
year: '2016'
...