19216911
Seminar
SoSe 15: EM Forschungsseminar "Seminar zur Diskreten Geometrie"
Raman Sanyal, Arnau Padrol Sureda
Kommentar
Inhalt:
Extensions of polytopes The extension complexity of a polytope P is the minimal number of facets of a polytope Q that linearly projects onto P. This rather simple definition has interesting consequences and relations to areas such as discrete geometry, combinatorial optimization, information theory, and linear algebra. Determining the extension complexity of a polytope is extremely hard (even for polygons!) and obtaining exact values or even just bounds for special polytopes is an active area of research. The goal of the seminar is to develop a good understanding of extension complexity and the notions related to it. Topics might include- geometry of extensions: sections, projections, and duality
- relations to the nonnegative rank of matrices
- lower bounds via coverings and chromatic numbers
- bounds via communication protocols
- special instances: permutahedra, matching polytopes, etc.
- other notions of extensions: the positive semidefinite and cone ranks
14 Termine
Regelmäßige Termine der Lehrveranstaltung
Di, 14.04.2015 14:00 - 16:00
Di, 21.04.2015 14:00 - 16:00
Di, 28.04.2015 14:00 - 16:00
Di, 05.05.2015 14:00 - 16:00
Di, 12.05.2015 14:00 - 16:00
Di, 19.05.2015 14:00 - 16:00
Di, 26.05.2015 14:00 - 16:00
Di, 02.06.2015 14:00 - 16:00
Di, 09.06.2015 14:00 - 16:00
Di, 16.06.2015 14:00 - 16:00
Di, 23.06.2015 14:00 - 16:00
Di, 30.06.2015 14:00 - 16:00
Di, 07.07.2015 14:00 - 16:00
Di, 14.07.2015 14:00 - 16:00
Inhalt:
Extensions of polytopes The extension complexity of a polytope P is the minimal number of facets of a polytope Q that linearly projects onto P. This rather simple definition ... Lesen Sie weiter