Abstract:

Let ${\rm EMBED}_{k\rightarrow 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 $\mathbb{R^d}$? Known results easily imply polynomiality of ${\rm EMBED}_{k\rightarrow 2}$ ($k=1,2$; the case $k=1$, $d=2$ is graph planarity) and of ${\rm EMBED}_{k\rightarrow 2k}$ for all $k > 2$ (even if $k$ is not considered fixed).

The main result presented in the talk is NP-hardness of ${\rm EMBED}_{2\rightarrow 4}$ and, more generally, of ${\rm EMBED}_{k\rightarrow d}$ for all $k,d$ with $d > 3$ and $d + 1 > k > (2d-3)/3$. We also show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that ${\rm EMBED}_{d\rightarrow d}$ and ${\rm EMBED}_{(d-1)\rightarrow d}$ are undecidable for each $d > 4$.

This is joint work with Jiri Matousek and Uli Wagner.