Javascript must be enabled

Christian Hasse : Perles at Bings House -- Facet Subgraphs of Simple Polytopes

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 & Koerner 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 stacked polytopes. 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 a simple modification of ``Bing's house'' (two walls removed) to construct explicit 4-dimensional counterexamples to Perles' conjecture.

Please select playlist name from following

Report Video

Please select the category that most closely reflects your concern about the video, so that we can review it and determine whether it violates our Community Guidelines or isn’t appropriate for all viewers. Abusing this feature is also a violation of the Community Guidelines, so don’t do it.


Comments Disabled For This Video