Hardness of almost embedding simplicial complexes in ℝ^d, II
share
A map f: K →ℝ^d of a simplicial complex is an almost embedding if f(σ) ∩ f(τ) = ∅ whenever σ, τ are disjoint simplices of K. Fix integers d,k ⩾ 2 such that k+2 ⩽ d ⩽3k/2+1. Assuming that the "preimage of a cycle is a cycle" we prove 𝐍𝐏-hardness of the algorithmic problem of recognition of almost embeddability of finite k-dimensional complexes in ℝ^d. Assuming that 𝐏𝐍𝐏 (and that the "preimage of a cycle is a cycle") we prove that the embedding obstruction is incomplete for k-dimensional complexes in ℝ^d using configuration spaces. Our proof generalizes the Skopenkov-Tancer proof of this result for d = 3k/2 + 1.
READ FULL TEXT