Shellings from relative shellings, with an application to NP-completeness
From MaRDI portal
Publication:2046454
DOI10.1007/s00454-020-00273-1zbMath1470.05173arXiv1906.01651OpenAlexW3132857487MaRDI QIDQ2046454
Andrés Santamaría-Galvis, Russ Woodroofe
Publication date: 18 August 2021
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1906.01651
General topology of complexes (57Q05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of simplicial complexes (05E45)
Related Items
Partitioning the projective plane and the dunce hat ⋮ NP-Hardness of Computing PL Geometric Category in Dimension 2
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Relative Stanley-Reisner theory and upper bound theorems for Minkowski sums
- Konstruktionsmethoden und das kombinatorische Homöomorphieproblem für Triangulationen kompakter semilinearer Mannigfaltigkeiten. (Methods of constructions and the combinatorical homeomorphism problem for triangulations of compact semilinear manifolds)
- Cohen-Macaulay quotients of polynomial rings
- Obstructions to shellability
- Combinatorial properties of ``cleanness
- Subdivisions, Shellability, and collapsibility of products
- Combinatorics and commutative algebra.
- Flag-symmetric and locally rank-symmetric partially ordered sets
- Constructible complexes and recursive division of posets
- The efficient certification of knottedness and Thurston norm
- Extremal examples of collapsible complexes and random discrete Morse theory
- On \(f\)- and \(h\)-vectors of relative simplicial complexes
- Knottedness is in NP, modulo GRH
- Decompositions of two-dimensional simplicial complexes
- On the shellability of the order complex of the subgroup lattice of a finite group
- Simplicial Manifolds, Bistellar Flips and a 16-Vertex Triangulation of the Poincaré Homology 3-Sphere
- Cohen-Macaulay rings and constructible polytopes
- A Representation of 2-dimensional Pseudomanifolds and its use in the Design of a Linear-Time Shelling Algorithm
- Which Spheres are Shellable?
- Two Decompositions in Topological Combinatorics with Applications to Matroid Complexes
- Shellable nonpure complexes and posets. II
- Shellable Nonpure Complexes and Posets. I
- Monomial Ideals
- Monomial Algebras
- Shellability is NP-complete
- Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
- Rings of Invariants of Tori, Cohen-Macaulay Rings Generated by Monomials, and Polytopes
- Recognition of collapsible complexes is NP-complete
