Dies ist der dritte Teil der Vorlesungsreihe Diskrete Geometrie. Die Vorlesung wird voraussichtlich auf Englisch gehalten werden. Daher folgt eine Beschreibung des Inhalts auf Englisch.
 
This is the third in a series of three courses on discrete geometry. This advanced course will cover a selection of the following topics (depending on the interests of the audience):
 
Departing from several equivalent definitions of generalized permutahedra, we will explore connections to matroids, tropical geometry, algebra, optimization...

 

Literatur

Submodular functions and optimization (Fujishige)
https://www.sciencedirect.com/bookseries/annals-of-discrete-mathematics/vol/58/suppl/C

Submodular Functions, Matroids, and Certain Polyhedra (Edmonds)
https://core.ac.uk/download/pdf/186613460.pdf

Combinatorial Optimization (Schrijver)
https://link.springer.com/book/9783540443896
Chapter 44: https://page.math.tu-berlin.de/~felsner/Lehre/SemMatS/Literatur/Schrijver-44:Submod+Polymat.pdf
Section 44.1 - important basics; Section 44.1a - many examples, also beyond the course content; Section 44.2 Greedy algorithm for submodular functions (the proof there uses LP duality, but the statements should be clear); Section 44.6c - Faces of polyhedra associated to submodular functions, partially beyond the course content. 

Matroid Theory (Oxley, 2011)
https://academic.oup.com/book/34846?login=false

The Bergman complex of a matroid and phylogenetic trees (Ardila & Klivans)
https://arxiv.org/abs/math/0311370
Section 2 & 3

Matroid polytopes, nested sets and Bergman fans (Feichtner & Sturmfels)
https://arxiv.org/abs/math/0411260
Section 2

Valuated matroids: a new look at the greedy algorithm (Dress & Wenzel)
https://www.sciencedirect.com/science/article/pii/089396599090009Z?via%3Dihub

Different approach for the ray representation of fine subdivision of Bergman fan:
Theorem 4.2.6 in
Introduction to Tropical Geometry (Maclagan &  Sturmfels)
https://bookstore.ams.org/view?ProductCode=GSM/161

Basics on matroid intersection
Section 5.1 & 5.2 in https://math.mit.edu/~goemans/18433S11/matroid-intersect-notes.pdf
Section 41.1 & 41.2 (including Königs' theorem): https://page.math.tu-berlin.de/~felsner/Lehre/SemMatS/Literatur/Schrijver-41:MatIntersection.pdf
Matroid mapping lemma: Section 2 here https://theory.stanford.edu/~jvondrak/MATH233B-2017/lec12.pdf

Submodular function minimization based on Lovasz extension - Section 1.1 & 1.2 in
https://theory.stanford.edu/~jvondrak/CS369P/lec17.pdf

Description of Wolfe's algorithm -- Section 1.1 in
The minimum Euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential
https://www.math.ucdavis.edu/~lrademac/wolfe_siam.pdf

For more details how to use a minimum-norm-point algorithm for submodular function minimization
The Minimum-Norm-Point Algorithm Applied to Submodular Function Minimization and Linear Programming
https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=6422fcb20b8ada016069fbae231c87783c2f5d8b

The original paper by Wolfe:
https://link.springer.com/article/10.1007/BF01580381
 

 

More Literature will follow. 

Zusätzliche Informationen

 

Die Zielgruppe sind Studenten mit einem soliden Hintergrund in diskreter Geometrie und/oder konvexer Geometrie (en par mit Discrete Geometry I & II). Die Themen dieses Kurses sind fortgeschrittene Themen in diskreter Geometrie, die Anwendungen und Inkarnationen in Differentialgeometrie, Topologie, Kombinatorik und algebraischer Geometrie finden.
 
Anforderungen: Vorzugsweise Diskrete Geometrie I und II.