Computing homotopy classes for diagrams

DOI10.1007/S00454-023-00513-0MaRDI QIDQ6050228zbMATH OpenOpenAlexFDO

Authors Marek Filakovský, Lukáš Vokřínek

Publication date 12 October 2023

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2104.10152

zbMATH Keywords

algorithmequivariant homotopyobstruction theoryTverberg-type problem

Mathematics Subject Classification ID

Equivariant homotopy theory in algebraic topology (55P91) Obstruction theory in algebraic topology (55S35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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{]}_G^A$ of homotopy classes of equivariant maps $ellcolonXoY$ extending a given equivariant map $fcolonAoY$ under the stability assumption $dim{X}^{H}leq2operatornameconn{Y}^H$ and $operatornameconn{Y}^{H}geq1$, for all subgroups $HleqG$. For fixed $n=operatornamedimX$, 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 $mathcal{I}^{m}athrmopomathsfsSet$, in the stable range $operatornamedimXleq2operatornameconnY$ and $operatornameconnY>1$, we give an algorithm that computes the set $[X,Y{]}^A$ of homotopy classes of maps of diagrams $ellcolonXoY$ extending a given $fcolonAoY$. Again, for fixed $n=dimX$, 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 $Komathbb{R}^d$ without $r$-tuple intersection points? In the metastable range of dimensions, $rdgeq(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).

Review text

The computation of homotopy invariants, such as the computation of the set of homotopy classes of maps, can generally be quite hard. From an algorithmic perspective, such computations are in most cases even undecidable, and they can be even harder in the equivariant setting. Building upon the previous works [\textit{M. Čadek} et al., SIAM J. Comput. 43, No. 5, 1728--1780 (2014; Zbl 1320.68099); Discrete Comput. Geom. 57, No. 4, 915--965 (2017; Zbl 1373.55018)], in the paper under review the authors present an algorithm to compute the set \([X,Y]_G^A\) of homotopy classes of \(G\)-equivariant maps from \(X\) to \(Y\) extending a given equivariant map \(A\to Y\). Here, \(X,Y\) and \(A\) denote finite simplicial sets equipped with the action of a finite group \(G\), and the algorithm is deduced under further assumptions on the dimension and connectivity of the fixed points subsets of \(X\) and \(Y\). Furthermore, if the dimension of \(X\) is fixed, the algorithm is shown to run in polynomial time. The main result of the paper was motivated by applications to the Tverberg-type problem, a generalization of the embeddability problem for simplicial complexes. In fact, Tverberg-type questions can be equivalently expressed in equivariant homotopic terms. The bridge with equivariant homotopy theory is provided by the Elmendorf's theorem [\textit{A. D. Elmendorf}, Trans. Am. Math. Soc. 277, 275--284 (1983; Zbl 0521.57027)], and it allows to focus on computing the homotopy classes of maps \([X,Y]^A\) (yielding the main result of the paper, Theorem~1.1). The proof uses tools from (equivariant) homotopy theory, such as obstruction theory and model categories, keeping an eye on the computational aspects.

Recommendations

• Algorithmic solvability of the lifting-extension problem
• Computing all maps into a sphere
• Computing all maps into a sphere
• Are two given maps homotopic? An algorithmic viewpoint
• Computing simplicial representatives of homotopy group elements
• Computing the abelian heap of unpointed stable homotopy classes of maps
• Invariant topological complexity
• User's guide to equivariant methods in combinatorics. II
• An isovariant Elmendorf's theorem
• scientific article; zbMATH DE number 146226

Cites work

• Algorithmic solvability of the lifting-extension problem
• Are two given maps homotopic? An algorithmic viewpoint
• Computing all maps into a sphere
• Constructive algebraic topology
• Effective homology for homotopy colimit and cofibrant replacement.
• Eliminating higher-multiplicity intersections. II. The deleted product criterion in the r-metastable range
• Equivariant cohomology theories
• Extendability of continuous maps is undecidable
• Finite computability of Postnikov complexes
• Heaps and unpointed stable homotopy theory
• scientific article; zbMATH DE number 1226952 (Why is no real title available?)
• scientific article; zbMATH DE number 206022 (Why is no real title available?)
• scientific article; zbMATH DE number 957983 (Why is no real title available?)
• On the groups \(H(\Pi,n)\). I
• On the groups \(H(\Pi,n)\). II
• Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension
• Systems of Fixed Point Sets

Cited in

(1)

• scientific article; zbMATH DE number 679776 (Why is no real title available?)

This page was built for publication: Computing homotopy classes for diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6050228)