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

Abstract

A map $f:K\to {\mathbb{R}}^d$ of a simplicial complex is an almost embedding if $f(\sigma )\cap f(\tau )=\varnothing$ whenever $\sigma ,\tau$ are disjoint simplices of $K$. Fix integers $d,k⩾2$ such that $k+2⩽d⩽\frac{3k}{2}+1$. Assuming that the "preimage of a cycle is a cycle" we prove $\mathbf{NP}$-hardness of the algorithmic problem of recognition of almost embeddability of finite $k$-dimensional complexes in ${\mathbb{R}}^d$. Assuming that $\mathbf{P}\ne \mathbf{NP}$ (and that the "preimage of a cycle is a cycle") we prove that the embedding obstruction is incomplete for $k$-dimensional complexes in ${\mathbb{R}}^d$ using configuration spaces. Our proof generalizes the Skopenkov-Tancer proof of this result for $d=\frac{3k}{2}+1$.

arXiv comment6 pages