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

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$. Theorem. Fix integers $d,k\ge 2$ such that $d=\frac{3k}{2}+1$. (a) Assume that $P\ne NP$. Then there exists a finite $k$-dimensional complex $K$ that does not admit an almost embedding in ${\mathbb{R}}^d$ but for which there exists an equivariant map $\tilde{K}\to S^{d-1}$. (b) The algorithmic problem of recognition almost embeddability of finite $k$-dimensional complexes in ${\mathbb{R}}^d$ is NP hard. The proof is based on the technique from the Matoušek-Tancer-Wagner paper (proving an analogous result for embeddings), and on singular versions of the higher-dimensional Borromean rings lemma and a generalized van Kampen--Flores theorem.

14 pages

Cited by in corpus (1)

• Some `converses' to intrinsic linking theorems