Author(s):

Čadek, Martin; Krčál, Marek; Vokřínek, Lukáš

Article Title: 
Algorithmic Solvability of the Lifting Extension Problem

Alternate Title: 
Discrete and Computational Geometry

Affiliation 
IST Austria 
Abstract: 
Let X and Y be finite simplicial sets (e.g. finite simplicial complexes), both equipped with a free simplicial action of a finite group G. Assuming that Y is dconnected and dimX≤2d, for some d≥1, we provide an algorithm that computes the set of all equivariant homotopy classes of equivariant continuous maps X→Y; the existence of such a map can be decided even for dimX≤2d+1. This yields the first algorithm for deciding topological embeddability of a kdimensional finite simplicial complex into Rn under the condition k≤23n−1. More generally, we present an algorithm that, given a liftingextension problem satisfying an appropriate stability assumption, computes the set of all homotopy classes of solutions. This result is new even in the nonequivariant situation.

Keywords: 
Homotopy classes; equivariant; fibrewise; liftingextension problem; algorithmic computation; Embeddability; Moore–Postnikov tower

Journal Title:

Discrete & Computational Geometry

Volume: 
54

Issue 
4

ISSN:

01795376

Publisher:

Springer

Date Published:

20170601

Start Page: 
915

End Page:

965

URL: 

DOI: 
10.1007/s0045401698556

Notes: 
The research of M. Č. was supported by the Project CZ.1.07/2.3.00/20.0003 of the Operational Programme Education for Competitiveness of the Ministry of Education, Youth and Sports of the Czech Republic. The research by M. K. was supported by the Center of Excellence—Inst. for Theor. Comput. Sci., Prague (Project P202/12/G061 of GA ČR) and by the Project LL1201 ERCCZ CORES. The research of L. V. was supported by the Center of Excellence—Eduard Čech Institute (Project P201/12/G028 of GA ČR).

Open access: 
yes (repository) 