Extendability of simplicial maps is undecidable

2020/08/02 by Skopenkov, A. · 1 citation
#55-02 #55P05 #55S36 #68-02 #68U05 #Algebraic Topology (math.AT) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2008.00492

Abstract

We present a short proof of the Čadek-Krčál-Matoušek-Vokřínek-Wagner result from the title (in the following form due to Filakovský-Wagner-Zhechev). For any fixed even l there is no algorithm recognizing the extendability of the identity map of S^l to a PL map X→ S^l of given 2l-dimensional simplicial complex X containing a subdivision of S^l as a given subcomplex. We also exhibit a gap in the Filakovský-Wagner-Zhechev proof that embeddability of complexes is undecidable in codimension >1.

Cited by

• Homotopy classification of closed polygonal lines: results and problems

Related

• Extendability of continuous maps is undecidable
• Hardness of almost embedding simplicial complexes in ℝ^d, II
• Hardness of embedding simplicial complexes in \R^d
• Topology of unavoidable complexes
• On Codimension one Embedding of Simplicial Complexes