Seminar (BaM-DAM-s, MaM-DASA-s)
Matroide in der
Kombinatorik, Geometrie und Optimierung
Sommersemester 2017
Aktuelles
- Bitte beachten Sie die Raumänderung.
- Vorbesprechung zum Seminar ist Dienstag, 18.
April im Raum 311, Robert-Mayer-Str. 10
Was
Matroide sind diskrete Strukturen die, wie der Name suggeriert,
Matrizen abstrahieren. Genauer gesagt sind Matroide eine kombinatorische
Abstraktion von linearer Unabhängigkeit die sich in vielen
Situationen finden lässt. Zum Beispiel sind
- Wälder in einem Graphen
- Teilmengen linear-unabhängiger Spalten einer Matrix
- Transversale von Mengensystemen
- Matchings in bipartiten Graphen
- Gitterpfade mit fixen Endpunkten
alles Matroide. Die gemeinsame Struktur ist nicht offensichtlich, oder?
In diesem Seminar wollen wir Matroide und ihre Anwendungen in
der Kombinatorik, der Geometrie und der Optimierung kennenlernen. Unter
anderem werden wir uns beschäftigen mit
- den bekannten und weniger bekannten Beispielen von Matroiden,
- verschiedenen Charakterisierungen von Matroiden,
- Greedy-Algorithmen und wann sie funktionieren,
- Polytopen von Matroiden und linearer Optimierung,
- Aufspannenden Bäumen und was man noch alles mit Hilfe von Matroiden zählen
kann,
und vieles mehr.
Wer
Die Themen streifen eine Vielzahl mathematischer Gebiete und sollten ein
breit-interessiertes Publikum ansprechen. Grundlagen aus diskreter Mathematik
sind notwendig, Wissen in Algebra, diskreter Geometrie oder Optimierung ist
sicher hilfreich.
Link zum Vorlesungsverzeichnis.
Wann und wo
Dienstags, 14-16, Robert-Mayer-Str. 10, Raum 311
Organisation / Spielregeln
Ziel des Seminars ist es allen Teilnehmern gleichermassen einen breiten
Überblick zu kombinatorischen, geometrischen und
optimierungs-theoretischen Aspekten von Matroiden zu geben. Das geschieht
durch Vorträge, die zum Teil aufeinander aufbauen. Entsprechend muss es das
Ziel jedes einzelnen Vortrags sein den Stoff klar und verständlich zu
präsentieren.
- Die Vorträge sind 60-70 Minuten, damit Zeit für Fragen und
Diskussionen bleibt.
- Es gibt 1-2 feste Treffen vor dem Vortag um Fragen zum
Inhalt zu klären und den Vortrag zu besprechen.
Das letzte Treffen findest mindestens eine Woche vor dem
Vortragstermin statt. Für das Treffen bitte Vortragsgliederung
(max. 2 Seiten) mitbringen. Sollten zwischenzeitlich Fragen zum
Thema auftreten, die Sie nicht sehr klären können, dann
einfach eine kurze Email schreiben (oder direkt vorbeikommen). Wir
können dann kurzfristig einen Termin ausmachen.
- Innerhalb von 2 Wochen nach dem Vortrag muss eine Ausarbeitung
(6-8 Seiten, bevorzugt LaTeX) abgegeben werden. Darin wird, aufbauend
auf der Vortragsgliederung, das Thema dargestellt. Die finalen
Ausarbeitungen werden dann mit allen Teilnehmern des Seminars
geteilt.
- Teilnahme am Seminar bedeutet insbesondere Teilnahme an
allen Vorträgen. In die Bewertung gehen ein: Eigenständigkeit
bei der Vorbereitung, Klarheit der mathematischen Argumentation und
Präsentationsfähigkeit.
- Anmeldung (mit Thema) erfolgt in der Vorbesprechung (siehe
oben).
Themen
Literatur
[A] |
Ardila,
Transversal and cotransversal matroids via their
representations.
|
[BdMN] |
Bonin, de Mier, Noy,
Lattice path matroids: enumerative aspects and Tutte
polynomials
|
[DW] |
Dunstan, Welsh,
greedy algorithm for solving a certain class of linear
programmes , Math. Programming 5 (1973), 338–353.
|
[GGMS] |
Gelfand et al.,
Combinatorial Geometries, Convex Polyhedra, and Schubert
Cells
|
[Ox] |
Oxley,
Matroid theory
|
[W] |
Welsh,
Matroid theory
|
[Wh] |
White (ed.),
Matroid applications
|
Impressum
Datenschutzerklärung