2013/07/24 by Čadek, Martin, Krčál, Marek, Vokřínek, Lukáš
#55P91 #55S35 #68U05 #Algebraic Topology (math.AT) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1307.6444
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 d-connected and dim X≤ 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 dim X≤ 2d+1. For fixed G and d, the algorithm runs in polynomial time. This yields the first algorithm for deciding topological embeddability of a k-dimensional finite simplicial complex into ℝn under the conditions k≤\frac 23 n-1. More generally, we present an algorithm that, given a lifting-extension problem satisfying an appropriate stability assumption, computes the set of all homotopy classes of solutions. This result is new even in the non-equivariant situation.