The combinatorial structure of a d-dimensional simple convex
polytope -- as given, for example, by the set of the (d-1)-regular
subgraphs of facets -- can be reconstructed from its abstract graph
[Blind & Mani 1988, Kalai 1988]. However, no
polynomial/efficient algorithm is known for this task, although a
polynomially checkable certificate for the correct reconstruction
exists [Kaibel & Korner 2000].
A much stronger certificate would be given by the following
characterization of the facet subgraphs, conjectured by M. Perles:
"The facet subgraphs of a simple d-polytope are exactly all
the (d-1)-regular, connected, induced, non-separating
subgraphs" [Perles 1970,1984].
We give examples for the validity of Perles conjecture: In particular,
it holds for the duals of cyclic polytopes, and for the duals of
On the other hand, we observe that for any counterexample, the
boundary of the (simplicial) dual polytope P* contains a
2-complex without a free edge, and without 2-dimensional
homology. Examples of such complexes are known; we use simple
modifications of Borsuk's ``dunce hat'' (one wall removed) and of
``Bing's house'' (two walls removed) to construct explicit
4-dimensional counterexamples to Perles' conjecture.