Other formats:
BibTeX
LaTeX
RIS
@article{2361467, author = {Filakovský, Marek and Vokřínek, Lukáš}, article_number = {3}, doi = {http://dx.doi.org/10.1007/s00454-023-00513-0}, keywords = {Equivariant homotopy; Algorithm; Tverberg-type problem}, language = {eng}, issn = {0179-5376}, journal = {Discrete and Computational Geometry}, title = {Computing Homotopy Classes for Diagrams}, url = {https://doi.org/10.1007/s00454-023-00513-0}, volume = {70}, year = {2023} }
TY - JOUR ID - 2361467 AU - Filakovský, Marek - Vokřínek, Lukáš PY - 2023 TI - Computing Homotopy Classes for Diagrams JF - Discrete and Computational Geometry VL - 70 IS - 3 SP - 866-920 EP - 866-920 PB - Springer SN - 01795376 KW - Equivariant homotopy KW - Algorithm KW - Tverberg-type problem UR - https://doi.org/10.1007/s00454-023-00513-0 N2 - 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. ER -
FILAKOVSKÝ, Marek and Lukáš VOKŘÍNEK. Computing Homotopy Classes for Diagrams. \textit{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.
|