Computing Homotopy Classes for Diagrams

FILAKOVSKÝ, Marek and Lukáš VOKŘÍNEK. Computing Homotopy Classes for Diagrams. Discrete and Computational Geometry. Springer, 2023, vol. 70, No 3, p. 866-920. ISSN 0179-5376. Available from: https://dx.doi.org/10.1007/s00454-023-00513-0.

Basic information

• Original name: Computing Homotopy Classes for Diagrams
• Authors: FILAKOVSKÝ, Marek and Lukáš VOKŘÍNEK (203 Czech Republic, belonging to the institution).
• Edition: Discrete and Computational Geometry, Springer, 2023, 0179-5376.

Other information

• Original language: English
• Type of outcome: Article in a journal
• Field of Study: 10101 Pure mathematics
• Country of publisher: United States of America
• Confidentiality degree: is not subject to a state or trade secret
• WWW: URL
• Impact factor: Impact factor: 0.800 in 2022
• RIV identification code: RIV/00216224:14310/23:00134379
• Organization unit: Faculty of Science
• Doi: http://dx.doi.org/10.1007/s00454-023-00513-0
• UT WoS: 001033657400003
• Keywords in English: Equivariant homotopy; Algorithm; Tverberg-type problem
• Tags: rivok
• Tags: International impact, Reviewed

Abstract

We present an algorithm that, given finite diagrams of simplicial sets X, A, Y, i.e., functors $${\mathcal {I}}^\textrm{op}\rightarrow {\textsf {s}} {\textsf {Set}}$$ I op → s Set , such that (X, A) is a cellular pair, $$\dim X\le 2\cdot {\text {conn}}Y$$ dim X ≤ 2 · conn Y , $${\text {conn}}Y\ge 1$$ conn Y ≥ 1 , computes the set $$[X,Y]^A$$ [ X , Y ] A of homotopy classes of maps of diagrams $$\ell :X\rightarrow Y$$ ℓ : X → Y extending a given $$f:A\rightarrow Y$$ f : A → Y . For fixed $$n=\dim X$$ n = dim X , the running time of the algorithm is polynomial. When the stability condition is dropped, the problem is known to be undecidable. Using Elmendorf’s theorem, we deduce an algorithm that, given finite simplicial sets X, A, Y with an action of a finite group G, computes the set $$[X,Y]^A_G$$ [ X , Y ] G A of homotopy classes of equivariant maps $$\ell :X\rightarrow Y$$ ℓ : X → Y extending a given equivariant map $$f:A\rightarrow Y$$ f : A → Y under the stability assumption $$\dim X^H\le 2\cdot {\text {conn}}Y^H$$ dim X H ≤ 2 · conn Y H and $${\text {conn}}Y^H\ge 1$$ conn Y H ≥ 1 , for all subgroups $$H\le G$$ H ≤ G . Again, for fixed $$n=\dim X$$ n = dim X , the algorithm runs in polynomial time. We further apply our results to Tverberg-type problem in computational topology: Given a k-dimensional simplicial complex K, is there a map $$K\rightarrow {\mathbb {R}}^d$$ K → R d without r-tuple intersection points? In the metastable range of dimensions, $$rd\ge (r+1) k+3$$ r d ≥ ( r + 1 ) k + 3 , the problem is shown algorithmically decidable in polynomial time when k, d, and r are fixed.

Links

• GBP201/12/G028, research and development project: Name: Ústav Eduarda Čecha pro algebru, geometrii a matematickou fyziku

Investor: Czech Science Foundation