Hardness of almost embedding simplicial complexes in $\mathbb R^d$
| Autor: | Skopenkov, Arkadiy, Tancer, Martin |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | Discr. and Comp. Geom. 61:2 (2019), 452-463 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1007/s00454-018-0013-1 |
| Popis: | A map $f\colon K\to \mathbb R^d$ of a simplicial complex is an almost embedding if $f(\sigma)\cap f(\tau)=\emptyset$ whenever $\sigma,\tau$ are disjoint simplices of $K$. Theorem. Fix integers $d,k\ge2$ 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\v{s}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. Comment: 14 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|