Convex polytopes in algebraic combinatorics

Winter Semester 2017/18

Introduction

Convex polytopes are sets of solutions for linear inequalities. The study of convex polytopes dates back at least to the ancient Babylonian and Egypt in the construction of pyramids. Motivated by different problems in pure and applied mathematics, contributions are made by Eudoxos, Plato, Euclid, Kepler, Descartes, Newton, Euler, Fourier, Legendre, Cauchy, Minkowski, Steinitz, Coxeter, to name but a few.

Algebraic combinatorics, as an interplay of algebra and combinatorics, applies methods from algebra to study combinatorial problems, and vice versa. This domain dates from the late eighties, and experienced considerable development in the last thirty years.

The goal of this lecture is to study convex polytopes arising from problems in linear algebra (eigenvalue problem of Hermitian matrices) and algebra (polynomial equations, a.k.a. ideals of polynomial rings). The first part of the lecture will be devoted to a guided tour in the zoo of polytopes (names, origins, species). After that we plan move to the lattice point counting problem (Ehrhart theory).

Informations

  • (26.10.2017) From 07.11.2017 on, the exercise session will be held in Seminarraum 3 (Raum 3.14), 16h15-17h45.
  • (19.10.2017) Change of time: due to the double session of Oberseminar Algebra, the first exercise session will be held on Tuesday 24.10.2017, 16h30-17h45, 15 minutes later than usual.
  • (19.10.2017) The exam will be held on 29.01.2018 during the lecture. More details will come later.
  • (12.10.2017) The first exercise session will be held on Tuesday 24.10.2017, 16h15-17h45, Stefan Cohn-Vossen Raum (Raum 3.13).
  • (09.10.2017) The lectures will be on Monday 16h-17h30 and Thursday 10h-11h30 in Seminarraum 3. Office hour will be on Monday 17h45-18h30 or by appointment.

    Exercises

    Exercise Sheet 1 (12.10.2017) will be discussed on 24.10.2017, please hand in your exercises in the lecture of 23.10.2017.
    Exercise Sheet 2 (23.10.2017) will be discussed on 07.11.2017, please hand in your exercises in the lecture of 06.11.2017.
    Exercise Sheet 3 (02.11.2017) will be discussed on 21.11.2017, please hand in your exercises in the lecture of 20.11.2017.
    Exercise Sheet 4 (16.11.2017) will be discussed on 05.12.2017, please hand in your exercises in the lecture of 04.12.2017.

    Contents

  • Lecture 1 (09.10.2017): Introduction.
  • Lecture 2 (12.10.2017): Affine subspaces.
  • Lecture 3 (16.10.2017): Convex subsets, polytopes.
  • Lecture 4 (19.10.2017): Weyl-Minkowski duality, examples.
  • Lecture 5 (23.10.2017): Examples, cones. (Permutahedron: 1,2)
  • Lecture 6 (26.10.2017): Examples, Fourier-Motzkin elimination.
  • Lecture 7 (30.10.2017): Farkas Lemma, polarity, Proof of Weyl-Minkowski duality for cones.
  • Lecture 8 (02.11.2017): Weyl-Minkowski duality for polytopes, dimension, volume.
  • Lecture 9 (06.11.2017): Polar dual of polytopes.
  • Lecture 10 (09.11.2017): Faces.
  • Lecture 11 (13.11.2017): Vertices.
  • Lecture 12 (16.11.2017): Facets.
  • Lecture 13 (20.11.2017): f-vectors, Euler formula, examples.
  • Lecture 14 (23.11.2017): Dehn-Sommerville theorem, posets.
  • Lecture 15 (27.11.2017): Poset, lattices, face lattices.
  • Lecture 16 (30.11.2017): Face lattices.
  • Lecture 17 (04.12.2017): Eigenvalues of Hermitian matrices.
  • Lecture 18 (07.12.2017): Gelfand-Tsetlin polytopes.
  • Lecture 19 (11.12.2017): Order polytopes and chain polytopes.
  • Lecture 20 (14.12.2017): Vertices, facets, volumes, face lattices....
  • Lecture 21 (18.12.2017): Marked order and marked chain polytopes.
  • Lecture 22 (21.12.2017):
  • Lecture 23 (08.01.2018):
  • Lecture 24 (11.01.2018):
  • Lecture 25 (15.01.2018):
  • Lecture 26 (18.01.2018):
  • Lecture 27 (22.01.2018): Revision.

    References

  • [0]. F. Ardila; T. Bliem; D.Salazar. Gelfand-Tsetlin polytopes and Feigin-Fourier-Littelmann-Vinberg polytopes as marked poset polytopes. J. Combin. Theory Ser. A 118 (2011), no. 8, 2454–2462.
  • [1]. A. Barvinok. Lattice Points, Polyhedra, and Complexity, IAS/Park City Mathematics Series, 2004.
  • [2]. D. Cox; J. Little; D. O’Shea. Using algebraic geometry. Second edition. Graduate Texts in Mathematics, 185. Springer, New York, 2005. xii+572 pp.
  • [3]. B. Matthias; R. Sinai. Computing the continuous discretely. Integer-point enumeration in polyhedra. Second edition. With illustrations by David Austin. Undergraduate Texts in Mathematics. Springer, New York, 2015. xx+285 pp.
  • [4]. P. Littelmann. Über Horns Vermutung, Geometrie, Kombinatorik und Darstellungstheorie. Jahresber. Deutsch. Math.-Verein. 110 (2008), no. 2, 75–99.
  • [5]. A. Postnikov. Permutohedra, associahedra, and beyond. International Mathematics Research Notices 2009, no. 6, 1026–1106.
  • [6]. B. Sturmfels. Polynomial Equations and Convex Polytopes. The American Mathematical Monthly. Vol. 105, No. 10 (Dec., 1998), pp. 907–922
  • [7]. R. Stanley. Two poset polytopes. Discrete Comput. Geom. 1 (1986), no. 1, 9–23.
  • [8]. R. Stanley. Enumerative combinatorics. Volume 1. Second edition. Cambridge Studies in Advanced Mathematics, 49. Cambridge University Press, Cambridge, 2012. xiv+626 pp.
  • [9]. B. Sturmfels. Gröbner bases and convex polytopes. University Lecture Series, 8. American Mathematical Society, Providence, RI, 1996. xii+162 pp.
  • [10]. G. Ziegler. Lectures on polytopes. Graduate Texts in Mathematics, 152. Springer-Verlag, New York, 1995. x+370 pp.

  • Arbeitsgruppe Algebra und Zahlentheorie, Mathematisches Institut, Universität zu Köln