2000/11/22 by Christian Haase, Günter M. Ziegler, Haase, Christian +1 · 1 citation
Computer Science · Mathematics · #05C75 (Secondary) #52B05 (Primary) #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.math/0011170
openalex publication_date 2000/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The combinatorial structure of a d-dimensional simple convex polytope can be reconstructed from its abstract graph [Blind & Mani 1987, Kalai 1988]. However, no polynomial/efficient algorithm is known for this task, although a polynomially checkable certificate for the correct reconstruction was found by [Joswig, Kaibel & Koerner 2000]. A much stronger certificate would be given by the following characterization of the facet subgraphs, conjectured by M. Perles: ``The facet subgraphs of the graph of a simple d-polytope are exactly all the (d-1)-regular, connected, induced, non-separating subgraphs'' [Perles 1970]. We give examples for the validity of Perles conjecture: In particular, it holds for the duals of cyclic polytopes, and for the duals of stacked polytopes. On the other hand, we identify a topological obstruction that must be present in any counterexample to Perles' conjecture; thus, starting with a modification of ``Bing's house'', we construct explicit 4-dimensional counterexamples.