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

DOI10.4171/JEMS/252zbMath1208.68130WikidataQ105336384 ScholiaQ105336384MaRDI QIDQ621847

Martin Tancer, Uli Wagner, Ji{ří} Matoušek

Publication date: 28 January 2011

Published in: Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

zbMATH Keywords

NP-hard(piecewise linear) embeddabilityalgorithmic unsolvabilityfinite simplicial complex

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Embeddings and immersions in PL-topology (57Q35)

Related Items

Algorithmic solvability of the lifting-extension problem, Geometric complexity of embeddings in \(\mathbb R^d\), Instability of the Smith index under joins and applications to embeddability, Untangling two systems of noncrossing curves, Some `converses' to intrinsic linking theorems, Finding non-orientable surfaces in 3-manifolds, The Complexity of Drawing Graphs on Few Lines and Few Planes, Extendability of simplicial maps is undecidable, Embedding dimensions of simplicial complexes on few vertices, PL Morse theory in low dimensions, Embeddings of \(k\)-complexes into \(2k\)-manifolds, On Codimension One Embedding of Simplicial Complexes, Unnamed Item, Hardness of almost embedding simplicial complexes in \(\mathbb {R}^d\), Stability of intersections of graphs in the plane and the van Kampen obstruction, Embedding 3-manifolds with boundary into closed 3-manifolds, Some Conjectures Concerning Complexity of PL subdivisions, The action dimension of right‐angled Artin groups, Coloring \(d\)-embeddable \(k\)-uniform hypergraphs, Non-embeddability of geometric lattices and buildings, Unnamed Item, The theta number of simplicial complexes, Computing all maps into a sphere, Computing simplicial representatives of homotopy group elements, Invariants of graph drawings in the plane, The van Kampen obstruction and its relatives, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On efficient sparse integer matrix Smith normal form computations
• Finite computability of Postnikov complexes
• Obstructions to the imbedding of a complex in a euclidean space. I: The first obstruction
• Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten
• An alternative proof that 3-manifolds can be triangulated
• The topology of four-dimensional manifolds
• Effectiveness - non effectiveness in semialgebraic and PL geometry
• The van Kampen obstruction and its relatives
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Quasi embeddings and embeddings of polyhedra in \(\mathbb{R}{}^ m\)
• On the classification of homeomorphisms of 2-manifolds and the classification of 3-manifolds
• Embeddings of polyhedra in \(\mathbb R^m\) and the deleted product obstruction
• On the generation of oriented matroids
• Algorithmic unsolvability of the triviality problem for multidimensional knots
• Einstein structures: Existence versus uniqueness
• Sachs' linkless embedding conjecture
• Van Kampen's embedding obstruction is incomplete for 2-complexes in \(\mathbb{R}^ 4\)
• Thin position and the recognition problem for \(S^ 3\)
• Charakterisierung der Komplexe der Ebene und der 2-Sphäre
• Computing spectral sequences
• The computational complexity of basic decision problems in 3-dimensional topology
• Embeddings of homology equivalent manifolds with boundary
• Homology and central series of groups
• The piecewise linear unknotting of cones
• \(\epsilon\)-mappings and generalized manifolds
• Plongements de polyedres dans le domaine metastable
• A note on polyhedra embeddable in the plane
• A proof of the most general polyhedral Schoenflies conjecture possible
• Products of cocycles and extensions of mappings
• A Nonpolyhedral Triangulated Mobius Strip
• The computational complexity of knot and link problems
• On the division of Euclidean n -space by topological ( n ─ 1)-spheres
• On the Polyhedral Schoenflies Theorem
• Effective algebraic topology
• Efficient Planarity Testing
• THE PROBLEM OF DISCRIMINATING ALGORITHMICALLY THE STANDARD THREE-DIMENSIONAL SPHERE
• Classification of sufficiently large three-dimensional manifolds
• Lectures on Polytopes
• Über wesentlich unplättbare Kurven im dreidimensionalen Raume
• Computational Complexity
• The computational complexity of knot genus and spanning area
• Toward a theory of crossing numbers
• Approximating Embeddings of Polyhedra In Codimension Three
• Computability Theory and Differential Geometry
• Computational Complexity
• Komplexe in euklidischen Räumen
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• Fast computation of the Smith form of a sparse integer matrix