Computing Homotopy Classes for Diagrams

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

FILAKOVSKÝ Marek VOKŘÍNEK Lukáš

Year of publication 2023
Type Article in Periodical
Magazine / Source Discrete and Computational Geometry
MU Faculty or unit

Faculty of Science

Citation
Web https://doi.org/10.1007/s00454-023-00513-0
Doi http://dx.doi.org/10.1007/s00454-023-00513-0
Keywords Equivariant homotopy; Algorithm; Tverberg-type problem
Description 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$$ l : 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$$ l : 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.