Abstract: Sei S eine Menge von n Punkten in der Ebene. Ein Spannbaum von S ist ein Baum, dessen Knoten die Punkte in S sind und dessen Kanten geradlinige Verbindungen zwischen Punkten sind. Ein Spannbaum heisst nichtkreuzend, wenn sich seine Kanten nicht überkreuzen. Im Vortrag werden Kantenoperationen untersucht, die verschiedene nichtkreuzende Spannbäume von S ineinander überführen. Wir zeigen, dass jeder solche Baum durch O(n2) verbessernde Kantenbewegungen in den minimalen Spannbaum von S transformiert werden kann, ohne dass Kreuzungen auftreten. Weiters wird gezeigt, dass beliebige nichtkreuzende Spannbäume durch `stetige' nichtkreuzende Kantenoperationen ineinander transformierbar sind. Beide Ergebnisse stützen sich auf einen allgemeinen Satz über Sequenzen von Spannbäumen, der im Vortrag bewiesen wird.
Kolloquium - 16 Uhr s.t.
Abstract: Wieviel Information über ein Polyeder benötigt man, um den kombinatorischen Typ rekonstruieren zu können? Diese zentrale Frage der Kombinatorik der Polyeder ist im Fall einfacher Polytope beantwortet: der Graph bestimmt den Seitenverband. Zum Beweis dieser Tatsache gibt es inzwischen eine wunderschöne Konstruktion von Gil Kalai, die aber leider algorithmisch jenseits von gut und böse ist. Wenn uns also jemand den Graph eines einfachen Polytops gibt, können wir tatsächlich - das heißt vor dem Weltenende - den Seitenverband rekonstruieren? Es würde genügen, die Teilgraphen der Facetten zu identifizieren. Bei 3-Polytopen sind dies genau die nicht-trennenden induzierten Kreise. Micha Perles vermutete, daß in allen Dimensionen die nicht-trennenden (d-1) regulären, (d-1)-zusammenhängenden induzierten Untergraphen genau die Facettengraphen sind. Ziel dieses Vortrags ist die Konstruktion eines Gegenbeispiels zur Perles Vermutung. Bisher müssen wir also Deep Thought noch lange rechnen lassen ...