Extendability of simplicial maps is undecidable

DOI10.1007/S00454-022-00454-0arXiv2008.00492MaRDI QIDQ6346325FDOQ6346325

Authors: A. B. Skopenkov 

Publication date: 2 August 2020

Abstract: We present a short proof of the v{C}adek-Krv{c}'al-Matouv{s}ek-Vokv{r}'inek-Wagner result from the title (in the following form due to Filakovsk'y-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 $Xo{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'y-Wagner-Zhechev proof that embeddability of complexes is undecidable in codimension $>1$.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) PL-topology (57Q99)

This page was built for publication: Extendability of simplicial maps is undecidable

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