Donnerstag, 24.04.08

14.00 Uhr

Mihyun Kang
Kombinatorische Strukturen und Algorithmen

Abstract:
Schwerpunkte der Forschung "Kombinatorische Strukturen und Algorithmen" sind Modellierung und Analyse struktureller und algorithmischer Fragen aus der diskreten Mathematik und aus der theoretischen Informatik. In diesem Vortrag werden speziell die folgenden drei Themengebiete diskutiert.

• Phasenübergänge: Evolution, Komponentenstrukturen und Phasenübergänge zufälliger Graphen und zufälliger Graphenprozesse

• Enumerative Kombinatorik: Anwendung der Singularitätenanalyse und der Matrixintegral-Methode, um die asymptotische Anzahl der kombinatorischen Strukturen zu berechnen

• Randomisierte Algorithmen: Randomizierte Algorithmen und deren Probabilistische Analyse, Erzeugung zufälliger kombinatorischer Strukturen

15.45 Uhr

Michael Huber
Designs, Codes, Komplexität

Abstract:
Die Frage nach der Existenz und Konstruktion bestimmter Konfigurationen ist von zentraler Bedeutung in der Diskreten Mathematik Insbesondere interessiert man sich für Konfigurationen mit stark regulären, symmetrischen Eigenschaften, wie beispielsweise einer reichen Automorphismengruppe. Neben ihrer besonderen mathematischen Ästhetik sind diese auch in den Anwendungen bedeutend, zum Beispiel bei der Übertragung und Speicherung von Information durch fehlerkorrigierende Codes.

Die Charakterisierung solcher Konfigurationen hinsichtlich ihrer Automorphismengruppe ist in den letzten Jahrzehnten auf reges Interesse gestoßen und gilt heute vielfach als natürliche Verallgemeinerung von Felix Kleins Erlanger Programm (1872). Im ersten Teil des Vortrages betrachten wir die Klassifikation aller kombinatorischen Steiner Designs mit einer fahnentransitiven Automorphismengruppe, einer wichtigen Charakterisierung hoch-symmetrischer Konfigurationen, die mehr als 40 Jahre offen geblieben war. Das Resultat verallgemeinert Arbeiten von Jacques Tits (1964) und Heinz Lüneburg (1965). Im Beweis spielen neben gruppentheoretischen, darstellungstheoretischen und inzidenzgeometrischen Methoden auch kombinatorische und zahlentheoretische Überlegungen eine entscheidende Rolle. Der knapper gehaltene, zweite Teil des Vortrages befasst sich mit der im Zusammenhang stehenden Entwicklung einer einheitlichen geometrischen Beschreibung der sporadischen einfachen Gruppen sowie dem engen Wechselspiel von Codierungstheorie und Algebraischer Kombinatorik. Ferner werden schwächere Varianten des Graphenisomorphieproblems für kombinatorische Designs thematisiert.

17.30 Uhr

Mathias Schacht
Extremale Kombinatorik

Abstract:
Typische Fragestellungen in der extremalen Kombinatorik untersuchen die Abhängigkeit von globalen Parametern bzw. der globalen Struktur diskreter Objekte, wie Graphen, Hypergraphen, Teilmengen der natürlichen Zahlen usw., unter lokalen Restriktionen. Der Satz von Turán aus der Graphentheorie ist ein klassischer Satz dieser Art, da er die kantenmaximalen Graphen, welche keinen vollständigen Untergraphen mit k>2 Knoten enthalten, beschreibt.

Nach einer kurzen Einführung in dieses Teilgebiet der Diskreten Mathematik und seinen Querverbindungen in andere Gebiete diskutieren wir Methoden und Resultate im Zusammenhang mit dem "Removal Lemma" für Hypergraphen, Gradbedingungen für spannende Graphen und Hypergraphen und dem Schwellenwertproblem in zufälligen Graphen.

Freitag, 25.04.08

8.30 Uhr

Amin Coja-Oghlan
Random discrete structures

Abstract:
Frequently the most effective (or, in fact, the only known) way to create a discrete object with certain properties is to choose one at random. Therefore, random discrete structures have been studied intensively since the pioneering work of Erdos and Renyi. While such random objects have many desirable properties, they have some very undesirable ones, too. For instance, it has been known for 30 years that very simple random inputs provide excellent worst-case examples for virtually all known algorithms. To shed some new light on this algorithmic aspect, I am going to discuss the recently observed connection between random structures and the theory of spin glasses, both as a sub-area of statistical physics and of probability theory.

10.15 Uhr

Daniela Kuehn
Hamiltonkreise, Matchings und verwandte Probleme

Abstract:
Ein Ergebnis von Dirac sagt, dass jeder Graph mit Minimalgrad n/2 einen Hamiltonkreis enthält. Thomassen fragte 1979 nach einem Analog für orientierte Graphen. (Ein orientierter Graph ist ein gerichteter Graph mit höchstens einer Kante zwischen je zwei Ecken.) Im ersten Teil des Vortrags werde ich eine Lösung dieses Problems vorstellen. Außerdem werde ich eine approximative Lösung einer Vermutung von Nash-Williams über Hamiltonkreise in Digraphen diskutieren und einige verwandte Probleme ansprechen

12.00 Uhr

Tibor Szabo
Unique sink orientations of cubes - what we know and what we don't

Abstract:
Unique sink orientation of cubes is a powerful combinatorial abstraction of linear programming. Besides the fact that the fastest known algorithms in the unit cost model do work in this setting, the concept is very flexible. On the one hand, it naturally admits the simplex algorithm, on the other hand it allows algorithms to "jump around" significantly. In the talk we overview the concept, its strength and limitations and also indicate the directions we think it is worthwhile to explore it further.

14.30 Uhr

Ilse Fischer
Über die Faszination von Plane Partitions und alternierenden Vorzeichenmatrizen

Abstract:
Plane Partitions, alternierende Vorzeichenmatrizen und verwandte Objekte treten in so verschiedenen Gebieten wie der Darstellungstheorie klassischer Gruppen und der statistischen Mechanik auf. Für Abzählkombinatoriker/innen sind diese Objekte besonders reizvoll, weil ihre Abzählung unter den verschiedensten Nebenbedingungen immer wieder zu schönen Produktformeln führt, die jedoch offenbar äußerst komplizierte Beweise erfordern. In meinem Vortrag stelle ich eine "polynomiale'' Methode vor, die ich im Laufe der letzten Jahre zur Abzählung dieser Objekte entwickelt habe. Mit ihrer Hilfe konnte ich unter anderem neue Beweise, Verfeinerungen und Verallgemeinerungen der Bender-Knuth (ex-)Vermutung und der Abzählung von alternierenden Vorzeichenmatrizen angeben. Weiters werde ich über Möglichkeiten diese Methode weiterzuentwickeln berichten, die unter anderem darauf beruhen, dass man Abzählprobleme solcher Art in der Regel auch als Abzählungen der ganzzahligen Punkten in gewissen rationalen Polytopen formulieren kann. Das legt nahe, dass es eine geometrische Erklärung für die Schönheit gewisser Abzählformeln geben könnte.

16.15 Uhr

Michael Joswig
"Phylogenetische Rekonstruktion und Splitzerlegungen von Polytopen"

Abstract:
In den 1980er Jahren haben Bandelt und Dress das Konzept des "tight spans" eines endlichen metrischen Raums entwickelt. Dies lässt sich anwenden auf das Problem der (Re-)Konstruktion von Abstammungsbäumen aus der Biologie. Ein wichtiger Schlüssel zum Verständnis sind sogenannte "Splits" endlicher metrischer Räume. Diese entsprechen geometrisch Zerlegungen des Hypersimplex $\Delta(2,n)$ in zwei maximale Zellen. Der Vortrag behandelt Splitzerlegungen beliebiger konvexer Polytope. Besonders interessant ist dies für allgemeine Hypersimplexe $\Delta(k,n)$ mit $k>2$. Am Ende des Vortrags wird auf Beziehungen zur tropischen Geometrie eingegangen.