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 $ k$-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.

E-Mail: kaibel@math.tu-berlin.de
Homepage: www.math.TU-Berlin.de/~kaibel


Zeitplan der Sektion   Tagesübersicht   Liste der Vortragenden