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

DOI10.1007/s00454-018-0013-1zbMath1415.57016arXiv1703.06305MaRDI QIDQ1716008

Martin Tancer, Arkadij B. Skopenkov

Publication date: 29 January 2019

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.06305

zbMATH Keywords

equivariant map; NP-hard; almost embedding; PL embedding

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

57Q35: Embeddings and immersions in PL-topology

05E45: Combinatorial aspects of simplicial complexes

Related Items

Invariants of graph drawings in the plane, Eliminating higher-multiplicity intersections. III. Codimension 2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hardness of embedding simplicial complexes in \(\mathbb R^d\)
• Obstructions to the imbedding of a complex in a euclidean space. I: The first obstruction
• Quasi embeddings and embeddings of polyhedra in \(\mathbb{R}{}^ m\)
• Embeddings of polyhedra in \(\mathbb R^m\) and the deleted product obstruction
• A Helly-type theorem for unions of convex sets
• On approximability by embeddings of cycles in the plane.
• Intuitive combinatorial topology. Transl. from the Russian by Abe Shenitzer. With the editorial assistance of John Stillwell
• Van Kampen's embedding obstruction is incomplete for 2-complexes in \(\mathbb{R}^ 4\)
• Eliminating higher-multiplicity intersections. III. Codimension 2
• Algorithmic solvability of the lifting-extension problem
• Geometric complexity of embeddings in \(\mathbb R^d\)
• Embeddings of homology equivalent manifolds with boundary
• Simplicial structures and transverse cellularity
• Plongements de polyedres dans le domaine metastable
• Tverberg's Theorem at 50: Extensions and Counterexamples
• THE PROBLEM OF DISCRIMINATING ALGORITHMICALLY THE STANDARD THREE-DIMENSIONAL SPHERE
• Beyond the Borsuk–Ulam Theorem: The Topological Tverberg Story
• Bounding Helly Numbers via Betti Numbers
• A user's guide to the topological Tverberg conjecture