Filakovský Marek, Vokřínek Lukáš
Department of Algebra, Charles University, Sokolovská 49/83, 186 75 Prague 8, Czech Republic.
Department of Mathematics and Statistics, Masaryk University, Kotlářská 2, 611 37 Brno, Czech Republic.
Discrete Comput Geom. 2023;70(3):866-920. doi: 10.1007/s00454-023-00513-0. Epub 2023 Jul 20.
We present an algorithm that, given finite diagrams of simplicial sets , , , i.e., functors , such that (, ) is a cellular pair, , , computes the set of homotopy classes of maps of diagrams extending a given . For fixed , 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 , , with an action of a finite group , computes the set of homotopy classes of equivariant maps extending a given equivariant map under the stability assumption and , for all subgroups . Again, for fixed , the algorithm runs in polynomial time. We further apply our results to Tverberg-type problem in computational topology: Given a -dimensional simplicial complex , is there a map without -tuple intersection points? In the metastable range of dimensions, , the problem is shown algorithmically decidable in polynomial time when , , and are fixed.
我们给出一种算法，给定单纯集的有限图表(X)、(Y)、(Z)，即函子(X)、(Y)、(Z)，使得((X, Y))是一个胞腔对，该算法计算扩展给定映射(f: Y \to Z)的图表映射(F: X \to Z)的同伦类集合([X, Z; Y, f])。对于固定的(X)、(Y)、(Z)，该算法的运行时间是多项式的。当去掉稳定性条件时，已知该问题是不可判定的。利用埃尔门多夫定理，我们推导出一种算法，给定具有有限群(G)作用的有限单纯集(X)、(Y)、(Z)，在稳定性假设(X^H \subseteq Y^H)和(Z^H)对所有子群(H \subseteq G)都是可缩的条件下，计算扩展给定等变映射(f: Y \to Z)的等变映射(F: X \to Z)的同伦类集合([X, Z; Y, f]_G)。同样，对于固定的(X)、(Y)、(Z)，该算法在多项式时间内运行。我们进一步将我们的结果应用于计算拓扑中的特弗伯格型问题：给定一个(d)维单纯复形(K)，是否存在一个没有(r)元交点的映射(f: K \to \mathbb{R}^{2r - d})？在维度的亚稳范围内，当(d)、(r)和(G)固定时，该问题在多项式时间内可算法判定。
