Logo der Freien Universität BerlinFreie Universität Berlin

Fachbereich Mathematik und Informatik


Service-Navigation

  • Startseite
Hinweise zur Datenübertragung bei der Google™ Suche
Fachbereich Mathematik und Informatik/Mathematik/Diskrete Geometrie/

Prof. Günter M. Ziegler

Menü
  • Forschung

    loading...

  • Publikationen

    loading...

  • Projekte

    loading...

  • Termine

    loading...

  • Lebenslauf

    loading...

  • Lehre

    loading...

  • Bilder

    loading...

  • Presse

    loading...

Mikronavigation

  • Startseite
  • Mathematik
  • Arbeitsgruppen
  • Diskrete Geometrie
  • Prof. Günter M. Ziegler
  • Publikationen_old
  • Examples and counterexamples for the Perles conjecture

Examples and counterexamples for the Perles conjecture

Christian Haase and Günter M. Ziegler – 2002

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.

Titel
Examples and counterexamples for the Perles conjecture
Verfasser
Christian Haase and Günter M. Ziegler
Datum
2002
Quelle/n
  • http://arxiv.org/abs/math/0011170v2
Erschienen in
Discrete & Computational Geometry, volume 28, pages 29-44
Art
Text

Termine

spinner

Neuigkeiten

spinner

Service-Navigation

  • Startseite

Diese Seite

  • Drucken
  • RSS-Feed abonnieren