M. Perles [2] conjectured that the facet subgraphs of a simple convex d-dimensional polytope are exactly the (d-1)-regular, connected, induced, non-separating subgraphs. The conjecture does hold for dimension three and smaller. However, Christian Haase and Günter M. Ziegler [1] proved that the conjecture does not hold in dimension four or greater. Based on their ideas we constructed a counterexample in dimension 4, which, however is smaller than the original construction. Counterexamples in higher dimensions may be obtained by wedging [1].

The counterexample presented here
(*perles.poly*) is a simple 4-polytope with 2592 vertices and 529
facets. The 3-regular, connected, induced, non-separating subgraph
which does not correspond to a facet has 1076 nodes. The construction
of Haase and Ziegler [1] (and the one presented here) actually produces a
counterexample to the dual version of the weak Perles conjecture in
dimension 4. Therefore the applet (*figure 1*) illustrates the
dual case: it depicts a modification of *Bing's House*, a 2-complex
without a free edge and without 2-dimensional homology. The core idea
of Haase and Ziegler is to embed *Bing's House* into the boundary
complex of the simplicial counterexample.

* Definition: A simplicial d-polytope *satisfies
the weak Perles conjecture

Haase and Ziegler [1] observed that for any (simplicial)
4-dimensional counterexample *Q* to the dual version of the weak
Perles conjecture, the boundary of *Q* contains a 2-complex
without a free edge, and without 2-dimensional homology. Examples of
such complexes are known and in the following a modification of
*Bing's House* is used to construct the counterexample.

This modification of *Bing's House* consists of two
rooms, the *UpperRoom* and the *LowerRoom*,
where each of them is connected to the outside via a `chimney' through
the other room (*figure 1*). The modified *Bing's House* can be embedded in a pile of 2*3*4 cubes,
triangulated as follows: Each cube is split into 6 tetrahedra, and the
tetrahedra are all grouped around one of the diagonal axes of the
cube. Add a cone over the boundary with apex *w* to get a
simplicial 3-sphere *C*. The
complex *C* is the boundary complex of a simplicial 4-polytope *Q*
and *C* contains a triangulation of the modified *Bing's House* as a
subcomplex. In the following
*C* will refer to the whole complex and *B* will refer to the subcomplex representing
*Bing's House*. Now the construction proceeds in a
series of stellar subdivisions on edges of *C*. Essentially these
subdivisions ensure that *B* becomes an induced subcomplex and
that *C* is `finely' triangulated: The subcomplex which in the
end will disprove the Perles conjecture will be composed of partial
vertex stars (of vertices in *B*) covering *B*. (Each
triangle of *B* is contained in exactly two of the chosen partial
vertex stars whose
intersection lies entirely in *B*.) Each tetrahedron of this
subcomplex must have exactly one free triangle, so the triangulation
must be fine enough to ensure that any two of the chosen partial
vertex stars do not intersect outside *B*.

In order to find the subcomplex in question, Haase and Ziegler [1]
give a coloring of the vertices of *B* such that the color of a
vertex determines which part of its vertex star (the part lying in
the *UpperRoom*, the part lying in the *LowerRoom* or the
part which lies in none of the rooms) is added to the subcomplex.

Finally we have to construct *Q*, a 4-polytope with the same
combinatorics as *C*. This process of `lifting' *C* into
*R ^{4}* is done as follows:

For a given *d*-polytope *P* consider the following
operation: transform *P* projectively by
moving a hyperplane to `infinity' which separates one vertex *w* of *P* from
the others. So, if the halfspace *H* defined by *H := {x in
R ^{d} : ax + a_{d+1} > 0}* contains all vertices
of

The aim is to reverse this process: Starting with *C* we try
to find fourth coordinates for its vertices such that we get *Q*
after a projective transformation with a hyperplane separating the apex
*w* from the other vertices.

In the construction of *C* we start
with the triangulated pile of 2*3*4 cubes described above. The
vertices of the cubical complex lie in
*Z ^{3}*. After adding the cone over the boundary with apex

At the end of their paper Haase and Ziegler [1] ask whether the
facet subgraphs of a simple 4-polytope are exactly the 3-regular,
3-connected, induced, non-separating and *planar*
subgraphs. For the example presented here, Petra Mutzel (Technical
University Vienna)
kindly examined the subgraph in question and proved its
non-planarity. This is not surprising, since the subgraph (with
its embedding) is a triangulation of *Bing's House*. Therefore this
example *is not* a counterexample to the proposed question.

In the following the content of *perles.poly* is described
briefly. The two sections which determine the counterexample are
VERTICES and the non standard section SUBGRAPH_NODES containing
the vertices which induce the 3-regular, 3-connected and
non-separating subgraph which does not correspond to a facet. Any
further section can be computed from this information, for example by
*polymake*, though computation might take some time. Therefore
some additional sections are included in the file. In the following a
complete list of the sections in *perles.poly*:

**standard sections**: VERTICES, BOUNDED, CENTERED, FACETS, VERTICES_IN_FACETS,
GRAPH, DIM, AMBIENT_DIM, SIMPLE, F_VECTOR, F2_VECTOR.

**non standard sections**: SUBGRAPH_NODES (the vertices inducing the
subgraph), SUBGRAPH, COMPL_SUBGRAPH (the subgraph induced by the
complementary set of vertices), SUBGRAPH_CONNECTIVITY, COMPL_SUBGRAPH_CONNECTIVITY.

Keywords | polytope, reconstructions, Perles conjecture, simplicial complex, lifting | |

MSC-2000 Classification | 52B11 | |

Zentralblatt No. | 05264890 |

- Christian Haase and Günter M. Ziegler:
*A counterexample to the Perles conjecture*, Discrete and Computational Geometry**28**(2002), 29-44. - Micha Perles:
*Results and problems on reconstruction of polytopes*, unpublished (1970).

- Master File: perles.poly
- Applet File: BingsHouse.jvx
- Preview: BingsHouse.gif
- Image: proj_transf.jpg

Submitted: Wed Mar 27 16:03:39 CET 2002.

Revised: Tue Nov 5 16:55:33 CET 2002.

Accepted: Wed Jan 29 12:17:06 CET 2003.

TU Berlin

Fakultät 2, Institut für Mathematik, MA 6-2

Strasse des 17. Juni 136

10623 Berlin, Germany

witte@math.tu-berlin.de