Mathematics – Combinatorics
Scientific paper
2000-11-22
Mathematics
Combinatorics
11 pages, 14 figures, see also http://www.math.tu-berlin.de/~ziegler
Scientific paper
The combinatorial structure of a d-dimensional simple convex polytope can be reconstructed from its abstract graph [Blind & Mani 1987, Kalai 1988]. However, no polynomial/efficient algorithm is known for this task, although a polynomially checkable certificate for the correct reconstruction was found by [Joswig, 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 the graph 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 identify a topological obstruction that must be present in any counterexample to Perles' conjecture; thus, starting with a modification of ``Bing's house'', we construct explicit 4-dimensional counterexamples.
Haase Christian
Ziegler Günter M.
No associations
LandOfFree
Examples and counterexamples for Perles' conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Examples and counterexamples for Perles' conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Examples and counterexamples for Perles' conjecture will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-590418