Enummeration und zufälliges Erzeugen

Teilprojekt der DFG-Forschergruppe "Algorithmen, Struktur, Zufall", in der außerdem Projekte der Arbeitgruppen von Prof. Dr. Günter Ziegler (TU Berlin), Prof. Dr. Martin Grötschel (Zuse-Institut Berlin) und Prof. Dr. Hans-Jürgen Prömel (HU Berlin) gefördert werden. In diesem letzten Jahr der Förderperiode werden insbesondere Beispiele untersucht, die eine Vermutung von Mihail und Vazirani über die Expansionseigenschaften der Graphen von 0/1-Polytopen unterstützen. Ein Beweis dieser Vermutung hätte weitreichende Folgen für das algorithmische Zählen komplexer kombinatorischer Objekte.