Hardness of almost embedding simplicial complexes in \(\mathbb {R}^d\) (Q1716008): Difference between revisions

The authors introduce notion of ``almost embedding'' of a finite $k$-dimensional simplicial complex $K$ in $\mathbb{R}^d$ and discuss related algorithmic problems. In case of embeddings of $|K| \to \mathbb{R}^d$ this problem has been treated in [\textit{J. Matoušek} et al., J. Eur. Math. Soc. (JEMS) 13, No. 2, 259--295 (2011; Zbl 1208.68130)]. If $\tilde{K}$ denotes the simplicial deleted product of $K$ and $f:|K| \to \mathbb{R}^d$ an almost embedding, then we have an equivariant map $\tilde{f}: \tilde{K} \to S^{d-1}$. The main result of the paper says that under some assumptions we may have $K$ and an equivariant map $\tilde{K} \to S^{d-1}$ but not an almost embedding of $|K|$. These assumptions are the following: P $\neq$ NP, $d, k \geq 2$ and $d=3k/2 + 1$. From the algorithmic point of view the problem of recognition of almost embeddability is NP-hard.