2021/04/20 by Filakovský, 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.2104.10152
We present an algorithm that, given finite simplicial sets X, A, Y with an action of a finite group G, computes the set [X,Y]AG of homotopy classes of equivariant maps ℓ \colon X → Y extending a given equivariant map f \colon A → Y under the stability assumption dim XH ≤ 2 conn YH and conn YH ≥ 1, for all subgroups H≤ G. For fixed n = dim X, the algorithm runs in polynomial time. When the stability condition is dropped, the problem is undecidable already in the non-equivariant setting. The algorithm is obtained as a special case of a more general result: For finite diagrams of simplicial sets X, A, Y, i.e. functors Iop → sSet, in the stable range dim X ≤ 2 conn Y and conn Y > 1, we give an algorithm that computes the set [X, Y]A of homotopy classes of maps of diagrams ℓ \colon X → Y extending a given f \colon A → Y. Again, for fixed n = dim X, the running time of the algorithm is polynomial. The algorithm can be utilized to compute homotopy invariants in the equivariant setting -- for example, one can algorithmically compute equivariant stable homotopy groups. Further, one can apply the result to solve problems from computational topology, which we showcase on the following Tverberg-type problem: Given a k-dimensional simplicial complex K, is there a map K → ℝd without r-tuple intersection points? In the metastable range of dimensions, rd ≥ (r+1)k +3, the result of Mabillard and Wagner shows this problem equivalent to the existence of a particular equivariant map. In this range, our algorithm is applicable and, thus, the r-Tverberg problem is algorithmically decidable (in polynomial time when k, d and r are fixed).