Hardness of embedding simplicial complexes in Rd Journal Article


Author(s): Matoušek, Jiří; Tancer, Martin; Wagner, Uli
Article Title: Hardness of embedding simplicial complexes in Rd
Affiliation
Abstract: Let EMBEDk→d be the following algorithmic problem: Given a finite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into Rd? Known results easily imply the polynomiality of EMBEDk→2 (k = 1; 2; the case k = 1, d = 2 is graph planarity) and of EMBEDk→2k for all k ≥ 3. We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBEDd→d and EMBED (d-1)→d are undecidable for each d ≥ 5. Our main result is the NP-hardness of EMBED2→4 and, more generally, of EMBED k→d for all k; d with d ≥ 4 and d ≥ k ≥ (2d - 2)/3. These dimensions fall outside the metastable range of a theorem of Haefliger and Weber, which characterizes embeddability using the deleted product obstruction. Our reductions are based on examples, due to Segal, Spież, Freedman, Krushkal, Teichner, and Skopenkov, showing that outside the metastable range the deleted product obstruction is not sufficient to characterize embeddability.
Journal Title: Journal of the European Mathematical Society
Volume: 13
Issue 2
ISSN: 1435-9863
Publisher: European Mathematical Society  
Date Published: 2011-01-01
Start Page: 259
End Page: 295
DOI: 10.4171/JEMS/252
Notes: We would like to thank Colin Rourke for explanations concerning PL topology and for examples showing the difference between PL embeddability and topological embeddability mentioned in Section 2. We also thank Michael Joswig, Gil Kalai, Frank Lutz, Alexander Nabutovsky, and Robin Thomas for kindly answering our questions. The second author would also like to thank Sergio Cabello for helpful discussions regarding linear-time algorithms for EMBED2!2. Finally, we are grateful to two anonymous referees for careful reading and valuable suggestions. Research of U.Wagner was supported by the Swiss National Science Foundation (SNF Projects 200021-116741 and 200021-125309).
Open access: no