Geometry and combinatorics of 0/1-polytopes.

• Applicant: Professor Dr. Günter M. Ziegler
• Subject Area: Mathematics
• Term: from 2001 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Units
• Subproject of: FOR 413: Algorithms, Structure, Randomness
• Participating Person: Professor Dr. Volker Kaibel