Seminar (BaM-DAM-s, MaM-DASA-s)

Matroide in der
Kombinatorik, Geometrie und Optimierung

Sommersemester 2017

Prof. Raman Sanyal





Aktuelles

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

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

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.

Themen

18.4. Vorbesprechung + "Definitions, concepts, and first examples" Raman Sanyal
25.4. Duality + Minors of matroids [Ox, Ch. 2] Stephan G.
2.5. Realizability of matroids [Ox,W] Christian S.
9.5. Transversal matroids [Ox, B] Anne S.
16.5. Realisierung von Transversal- und Kotransversalmatroiden [Ardilla] Marvin B.
23.5. Heiratssatz und Verallgemeinerungen [Ox, Ch. 12.2] Bilal S.
30.5. Matroide und geometrische Verbände [Ox, Ch. 1.7] Carsten T.
6.6. Greedy-Algorithmus und Matroide [Ox, Ch. 1.8] David K.
13.6. Polytope und Matroid-Polytope [GGMS, Sect. 4] Johanna K.
3.7. Lattice-Path Matroide [BdMN] Thomas F.

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