Computing Homotopy Classes for Diagrams

J 2023

Computing Homotopy Classes for Diagrams

FILAKOVSKÝ, Marek a Lukáš VOKŘÍNEK

Základní údaje

Originální název

Computing Homotopy Classes for Diagrams

Autoři

FILAKOVSKÝ, Marek a Lukáš VOKŘÍNEK (203 Česká republika, domácí)

Vydání

Discrete and Computational Geometry, Springer, 2023, 0179-5376

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.800 v roce 2022

Kód RIV

RIV/00216224:14310/23:00134379

Organizační jednotka

Přírodovědecká fakulta

DOI

http://dx.doi.org/10.1007/s00454-023-00513-0

UT WoS

001033657400003

Klíčová slova anglicky

Equivariant homotopy; Algorithm; Tverberg-type problem

Štítky

rivok

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 16. 1. 2024 09:18, Mgr. Marie Šípková, DiS.

Anotace

V originále

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.

Návaznosti

GBP201/12/G028, projekt VaV

Název: Ústav Eduarda Čecha pro algebru, geometrii a matematickou fyziku

Investor: Grantová agentura ČR, Ústav Eduarda Čecha pro algebru, geometrii a matematickou fyziku

Citovat

FILAKOVSKÝ, Marek a Lukáš VOKŘÍNEK. Computing Homotopy Classes for Diagrams. Discrete and Computational Geometry. Springer, 2023, roč. 70, č. 3, s. 866-920. ISSN 0179-5376. Dostupné z: https://dx.doi.org/10.1007/s00454-023-00513-0.

@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 a Lukáš VOKŘÍNEK. Computing Homotopy Classes for Diagrams. \textit{Discrete and Computational Geometry}. Springer, 2023, roč.~70, č.~3, s.~866-920. ISSN~0179-5376. Dostupné z: https://dx.doi.org/10.1007/s00454-023-00513-0.

Podrobný výpis o publikaci