Examples and counterexamples for Perles' conjecture
| dc.creator | Haase, Christian | |
| dc.creator | Ziegler, Günter M. | |
| dc.date | 2000-11-22 | |
| dc.date | 2001-07-19 | |
| dc.date.accessioned | 2026-07-07T06:32:50Z | |
| dc.date.available | 2026-07-07T06:32:50Z | |
| dc.description | 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. | |
| dc.description | 11 pages, 14 figures, see also http://www.math.tu-berlin.de/~ziegler | |
| dc.identifier | https://arxiv.org/abs/math/0011170 | |
| dc.identifier | http://arxiv.org/abs/math/0011170 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/98994 | |
| dc.subject | Combinatorics | |
| dc.subject | 52B05 (Primary); 05C75 (Secondary) | |
| dc.title | Examples and counterexamples for Perles' conjecture | |
| dc.type | text |