Examples and counterexamples for the Perles conjecture (Q1611070)

The combinatorial structure of a \(d\)-dimensional simple convex polytope can be reconstructed from its abstract graph. No polynomial algorithm is known for this, although a polynomially checkable certificate for the correct reconstruction exists. The following conjecture by Micha Perles would provide a much stronger certificate: ``The facet subgraphs of a simple \(d\)-polytope are exactly all the \((d-1)\)-regular, connected, induced, non-separating subgraphs.'' The authors present non-trivial classes of examples for the validity of the Perles conjecture. In particular, it holds for the duals of the cyclic polytopes, and for the duals of stacked polytopes. On the other hand, the authors observe that for any \(4\)-dimensional counterexample, the boundary of the (simplicial) dual polytope \(P^{\Delta}\) contains a \(2\)-complex without a free edge, and without \(2\)-dimensional homology. Examples of such complexes are known; using a modification of ``Bing's house'' (two walls removed) the authors construct explicit \(4\)-dimensional counterexamples to the Perles conjecture.