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).

Grades

Grades from the final exam

Informations

  • (01.03.2018) The Nachklausur will be an oral exam for 45 minutes. After your registration, please send me an e-mail to fix the schedule for the afternoon of 21.03.2018.
  • (18.01.2018) The Klausureinsicht will be on 01.02.2018, 11h, Seminarraum 3 (Room 3.14).
  • (18.01.2018) The Nachklausur will be on 21.03.2018, Seminarraum 2, starting from 14h.
  • (18.01.2018) Please find the solution to Exercise 5, Sheet 5 here.
  • (11.01.2018) Please register for exam on KLIPS, and let me (or Frau Georg) know if you have difficulty.
  • (11.01.2018) I forgot the following condition in the construction of Newton-Okounkov body in the lecture: the total ordering should be chosen such that the minimal monomials of P_1,...,P_r are different.
  • (21.12.2017) The paper of Jochemko-Sanyal, Pegel mentioned in the lecture can be found by clicking the names.
  • (21.12.2017) Please find the solution to Exercise 4, Sheet 4 here.
  • (12.12.2017) Exercise Sheet 5: (optional exercise) n-cube -> d-cube.
  • (27.11.2017) Hints for Exercise Sheet 4: (1). Exercise 4 on edges of Birkhoff polytopes: if \sigma^{-1}\tau is not a cycle, then it is the multiplication of at least two cycles, try to find another two vertices X, Y such that the segment S_{X,Y} cross the segment in the exercise. (2). Exercise 5, the last optional question: notice that the 4-cube has f-vector (16,32,24,8).
  • (23.11.2017) The last lecture is the one on 22.01.2018 (no lecture on 25.01.2018). The exam will be held on 29.01.2018, 16h-18h in Hoersaal H230, COPT Gebaeude (for a map click here).
  • (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.
    Exercise Sheet 5 (30.11.2017) will be discussed on 19.12.2017, please hand in your exercises in the lecture of 18.12.2017.
    Exercise Sheet 6 (14.12.2017) will be discussed on 16.01.2018, please hand in your exercises in the lecture of 11.01.2018.

    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): 3-polytopes, Dehn-Sommerville theorem.
  • Lecture 15 (27.11.2017): Poset, lattices, face lattices.
  • Lecture 16 (30.11.2017): Face lattices.
  • Lecture 17 (04.12.2017): Equivalences of polytopes. Hermitian matrices.
  • Lecture 18 (07.12.2017): Eigenvalue problems. (for the proof of Lemma 3.3, see Lemma 5 in this paper)
  • Lecture 19 (11.12.2017): Gelfand-Tsetlin polytope.
  • Lecture 20 (14.12.2017): Order polytope.
  • Lecture 21 (18.12.2017): Face lattice of order polytopes. Chain polytope.
  • Lecture 22 (21.12.2017): Marked order and marked chain polytopes. Gelfand-Tsetlin and Feigin-Fourier-Littelmann-Vinberg polytopes.
  • Lecture 23 (08.01.2018): Newton polytopes.
  • Lecture 24 (11.01.2018): Baby Kouchnirenko-Bernstein theorem, Newton-Okounkov bodies.
  • Lecture 25 (15.01.2018): Mixed volumes.
  • Lecture 26 (18.01.2018): Kouchnirenko-Bernstein theorem, Ehrhart theory.
  • Lecture 27 (22.01.2018): Ehrhart theory, 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