Geometrie und Kombinatorik von 0/1-Polytopen

• Antragsteller: Professor Dr. Günter M. Ziegler
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2001 bis 2008
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5467699

0/1-Polytope sind fundamentale mathematische Objekte: Polyeder, deren Ecken nur 0/1-Koordinaten haben. Diese Definition klingt einfach, die Struktur von 0/1-Polytopen kann trotzdem - wie sich in den vergangenen Jahren gezeigt hat - bemerkenswert kompliziert sein. Sie sind aber auch interessant und wichtig: Einsichten in die Struktur von speziellen Beispielen haben in den vergangenen Jahrzehnten zu dramatischen Fortschritten in der Kombinatorischen Optimierung geführt, beispielsweise bei der Lösung von großen Travelling-Salesman- und Schnitt-Problemen. Während spezielle 0/1-Polytope dafür sehr intensiv studiert wurden, ist jedoch wenig allgemeine Theorie dazu entwickelt worden. Im beantragten Projekt wollen wir deshalb gezielt gewisse Struktureigenschaften von allgemeinen 0/1-Polytopen untersuchen. Dabei spielt der Zufall zwei Rollen: einerseits untersucht man zufällige (d.h. "typische") 0/1-Polytope, auch um die speziellen Polytope der kombinatorischen Optimierung darauf zu prüfen, ob sie "typisch" oder extremal sind. Andererseits geht es um Methoden, um auf gegebenen Polytopen effektiv zufällige Ecken zu finden: dies ist der entscheidende Zwischenschritt für moderne Methoden für das "approximative Zählen" (vgl. Teilprojekt 7).

• DFG-Verfahren: Forschungsgruppen
• Teilprojekt zu: FOR 413: Algorithmen, Struktur, Zufall
• Beteiligte Person: Professor Dr. Volker Kaibel