Examples and Counterexamples for the Perles Conjecture

   Abstract. The combinatorial structure of a d -dimensional simple convex polytope—as given, for example, by the set of the (d-1) -regular subgraphs of the facets—can be reconstructed from its abstract graph. However, no polynomial/ efficient algorithm is known for this task, although a polynomially checkable certificate for the correct reconstruction exists. A much stronger certificate would be given by the following characterization of the facet subgraphs, conjectured by Micha Perles: ``The facet subgraphs of a simple d-polytope are exactly all the (d-1) -regular, connected, induced, non-separating subgraphs .' We present non-trivial classes of examples for the validity of the Perles conjecture: in particular, it holds for the duals of cyclic polytopes, and for the duals of stacked polytopes. On the other hand, we observe that for any 4-dimensional counterexample, the boundary of the (simplicial) dual polytope contains a 2 -complex without a free edge, and without 2-dimensional homology. Examples of such complexes are known; we use a modification of ``Bing's house' (two walls removed) to construct explicit 4-dimensional counterexamples to the Perles conjecture.