Hardness of embedding simplicial complexes in ${\mathbb{R}}^d$

Abstract

Let EMBED(k,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 R^d? Known results easily imply polynomiality of EMBED(k,2) (k=1,2; the case k=1, d=2 is graph planarity) and of EMBED(k,2k) for all k>2 (even if k is not considered fixed). We observe that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBED(d,d) and EMBED(d-1,d) are undecidable for each d>4. Our main result is NP-hardness of EMBED(2,4) and, more generally, of EMBED(k,d) for all k,d with d>3 and d\geq k \geq (2d-2)/3. These dimensions fall outside the so-called 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.

36 pages, 17 figures; revised version incorporating changes suggested by anonymous referees; added linear-time algorithm for deciding planarity of 2-dimensional complexes

References in corpus (2)

• Algorithmic aspects of homeomorphism problems
• m-structures determine integral homotopy type

Cited by in corpus (8)

• The van Kampen obstruction and its relatives
• Eliminating Higher-Multiplicity Intersections, I. A Whitney Trick for Tverberg-Type Problems
• Combinatorics of embeddings
• Embedding 3-manifolds with boundary into closed 3-manifolds
• PL Morse theory in low dimensions
• Stability of intersections of graphs in the plane and the van Kampen obstruction
• Fitting a Simplicial Complex using a Variation of k-means
• Geometric representations of binary codes embeddable in three dimensions