Computing Homotopy Classes for Diagrams

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F23%3A00134379" target="_blank" >RIV/00216224:14310/23:00134379 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/23:10471406

Výsledek na webu

<a href="https://doi.org/10.1007/s00454-023-00513-0" target="_blank" >https://doi.org/10.1007/s00454-023-00513-0</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00454-023-00513-0" target="_blank" >10.1007/s00454-023-00513-0</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Computing Homotopy Classes for Diagrams

Popis výsledku v původním jazyce

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 Xle 2cdot {text {conn}}Y$$ dim X ≤ 2 · conn Y , $${text {conn}}Yge 1$$ conn Y ≥ 1 , computes the set $$[X,Y]^A$$ [ X , Y ] A of homotopy classes of maps of diagrams $$ell :Xrightarrow Y$$ ℓ : X → Y extending a given $$f:Arightarrow 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 :Xrightarrow Y$$ ℓ : X → Y extending a given equivariant map $$f:Arightarrow Y$$ f : A → Y under the stability assumption $$dim X^Hle 2cdot {text {conn}}Y^H$$ dim X H ≤ 2 · conn Y H and $${text {conn}}Y^Hge 1$$ conn Y H ≥ 1 , for all subgroups $$Hle 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 $$Krightarrow {mathbb {R}}^d$$ K → R d without r-tuple intersection points? In the metastable range of dimensions, $$rdge (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ázev v anglickém jazyce

Computing Homotopy Classes for Diagrams

Popis výsledku anglicky

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 Xle 2cdot {text {conn}}Y$$ dim X ≤ 2 · conn Y , $${text {conn}}Yge 1$$ conn Y ≥ 1 , computes the set $$[X,Y]^A$$ [ X , Y ] A of homotopy classes of maps of diagrams $$ell :Xrightarrow Y$$ ℓ : X → Y extending a given $$f:Arightarrow 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 :Xrightarrow Y$$ ℓ : X → Y extending a given equivariant map $$f:Arightarrow Y$$ f : A → Y under the stability assumption $$dim X^Hle 2cdot {text {conn}}Y^H$$ dim X H ≤ 2 · conn Y H and $${text {conn}}Y^Hge 1$$ conn Y H ≥ 1 , for all subgroups $$Hle 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 $$Krightarrow {mathbb {R}}^d$$ K → R d without r-tuple intersection points? In the metastable range of dimensions, $$rdge (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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GBP201%2F12%2FG028" target="_blank" >GBP201/12/G028: Ústav Eduarda Čecha pro algebru, geometrii a matematickou fyziku</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete and Computational Geometry

ISSN

0179-5376

e-ISSN

1432-0444

Svazek periodika

70

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

55

Strana od-do

866-920

Kód UT WoS článku

001033657400003

EID výsledku v databázi Scopus

2-s2.0-85165252808