Examples and Counterexamples for Perles' Conjecture

Christian Haase & G\"unter M. Ziegler

To appear at Formal Power Series and Algebraic Combinatorics (FPSAC01), Tempe, Arizona (USA), May 20-26, 2001


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 & K\"orner 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]. 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 observe that for any 4-dimensional 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 a simple modification of ``Bing's house'' (two walls removed) to construct explicit 4-dimensional counterexamples to Perles' conjecture.

Server START Conference Manager
Update Time 23 Feb 2001 at 08:48:05
Maintainer maylis@labri.u-bordeaux.fr.
Start Conference Manager
Conference Systems