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

Jiří Matoušek; Martin Tancer; Uli Wagner

Journal of the European Mathematical Society (2011)

- Volume: 013, Issue: 2, page 259-295
- ISSN: 1435-9855

## Access Full Article

top## Abstract

top## How to cite

topMatoušek, Jiří, Tancer, Martin, and Wagner, Uli. "Hardness of embedding simplicial complexes in $\mathbb {R}^d$." Journal of the European Mathematical Society 013.2 (2011): 259-295. <http://eudml.org/doc/277789>.

@article{Matoušek2011,

abstract = {Let $\texttt \{EMBED\}_\{k\rightarrow d\}$ be the following algorithmic problem: Given a ﬁnite simplicial complex $K$ of dimension at most $k$, does there exist a (piecewise linear) embedding of $K$ into $\mathbb \{R\}^d$? Known results easily imply polynomiality of $\texttt \{EMBED\}_\{k\rightarrow 2\}$ ($k = 1, 2$; the case $k = 1, d = 2$ is graph planarity) and of $\texttt \{EMBED\}_\{k\rightarrow 2k\}$ for all $k\ge 3$. We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that $\texttt \{EMBED\}_\{d\rightarrow d\}$ and $\texttt \{EMBED\}_\{(d-1)\rightarrow d\}$ are undecidable for each $_d\ge 5$. Our main result is NP-hardness of $\texttt \{EMBED\}_\{2\rightarrow 4\}$ and, more generally, of $\texttt \{EMBED\}_\{k\rightarrow d\}$ for all $k$, $d$ with $d\ge 4$ and $d\ge k \ge (2d-2)/3$. These dimensions fall outside the metastable range of a theorem of Haeﬂiger and Weber, which characterizes embeddability using the deleted product obstruction. Our reductions are based on examples, due to Segal, Spiez, Freedman, Krushkal, Teichner, and Skopenkov, showing that outz side the metastable range the deleted product obstruction is not suffcient to characterize embeddability.},

author = {Matoušek, Jiří, Tancer, Martin, Wagner, Uli},

journal = {Journal of the European Mathematical Society},

keywords = {algorithmic unsolvability; finite simplicial complex; (piecewise linear) embeddability; NP-hard; algorithmic unsolvability; finite simplicial complex; (piecewise linear) embeddability; NP-hard},

language = {eng},

number = {2},

pages = {259-295},

publisher = {European Mathematical Society Publishing House},

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

url = {http://eudml.org/doc/277789},

volume = {013},

year = {2011},

}

TY - JOUR

AU - Matoušek, Jiří

AU - Tancer, Martin

AU - Wagner, Uli

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

JO - Journal of the European Mathematical Society

PY - 2011

PB - European Mathematical Society Publishing House

VL - 013

IS - 2

SP - 259

EP - 295

AB - Let $\texttt {EMBED}_{k\rightarrow d}$ be the following algorithmic problem: Given a ﬁnite simplicial complex $K$ of dimension at most $k$, does there exist a (piecewise linear) embedding of $K$ into $\mathbb {R}^d$? Known results easily imply polynomiality of $\texttt {EMBED}_{k\rightarrow 2}$ ($k = 1, 2$; the case $k = 1, d = 2$ is graph planarity) and of $\texttt {EMBED}_{k\rightarrow 2k}$ for all $k\ge 3$. We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that $\texttt {EMBED}_{d\rightarrow d}$ and $\texttt {EMBED}_{(d-1)\rightarrow d}$ are undecidable for each $_d\ge 5$. Our main result is NP-hardness of $\texttt {EMBED}_{2\rightarrow 4}$ and, more generally, of $\texttt {EMBED}_{k\rightarrow d}$ for all $k$, $d$ with $d\ge 4$ and $d\ge k \ge (2d-2)/3$. These dimensions fall outside the metastable range of a theorem of Haeﬂiger and Weber, which characterizes embeddability using the deleted product obstruction. Our reductions are based on examples, due to Segal, Spiez, Freedman, Krushkal, Teichner, and Skopenkov, showing that outz side the metastable range the deleted product obstruction is not suffcient to characterize embeddability.

LA - eng

KW - algorithmic unsolvability; finite simplicial complex; (piecewise linear) embeddability; NP-hard; algorithmic unsolvability; finite simplicial complex; (piecewise linear) embeddability; NP-hard

UR - http://eudml.org/doc/277789

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.