15. ÖMG-Kongress
Jahrestagung der Deutschen Mathematikervereinigung
16. bis 22. September 2001 in Wien
Sektion 3 - Diskrete Mathematik, Algorithmen
Dienstag, 18. September 2001, 17.00, Hörsaal 23
Rekonstruktion von einfachen Polytopen aus ihren Graphen
Volker Kaibel, TU Berlin
(Koautoren: Michael Joswig, Friederike Körner)
Blind und Mani [1] bewiesen 1987, dass die kombinatorische Struktur
eines einfachen konvexen Polytops (d.h., seine Ecken-Facetten
Inzidenzstruktur) nur von seinem Graphen abhängt. Kalai [2] fand
1988 einen sehr eleganten und konstruktiven Beweis für dieses
Resultat. Allerdings läß t sich die Laufzeit von Kalais
Algorithmus nur exponentiell in der Größ e des Graphen
abschätzen. Der Komplexitätsstatus des Problems, die
Ecken-Facetten Inzidenzen eines einfachen Polytops aus seinem Graph zu
rekonstruieren, blieb damit offen. Indem wir das Konzept der
-Systeme des Graphen eines einfachen Polytops einführen, können
wir Kalais Ansatz zu einer guten Charakterisierung (im Sinne von
Edmonds) der Ecken-Facetten Inzidenzen eines einfachen Polytops
fortführen. Wir zeigen, dass das Rekonstruktionsproblem als ein
kombinatorisches Optimierungsproblem formuliert werden kann, zu
welchem ein streng duales Optimierungsproblem existiert. Die
Lösungen dieses dualen Problems sind die abstrakten Zielfunktionen
des Polytops, d.h., die Schälungsordnungen des Randes seines dualen
Polytops.
| [1] |
R. Blind and P. Mani-Levitska, On puzzles and polytope isomorphisms,
Aequationes Math. 34 (1987), 287-297. |
| [2] |
G. Kalai, A simple way to tell a simple polytope from its graph, J.
Comb. Theory, Ser. A 49 (1988), 381-383. |
Zeitplan der Sektion
Tagesübersicht
Liste der Vortragenden