# Math 697: Topics in combinatorics: polytopes

Instructor: Alejandro H. Morales
ahmorales at math dot umass dot edu

Class schedule: MWF 11:15 - 12:05 pm, LGRT 171

Office Hours: MW 1pm-2pm, T 9:30-10:30am, LGRT 1120

Course description: This course is an introduction to the theory of convex polytopes and their applications to algebraic combinatorics. The course will cover basic facts and properties of polytopes including faces of polytopes, valuation theory, Ehrhart theory, triangulations, zonotopes and tilings. We will also tentatively cover the following families of polytopes with interest in other fields: root polytopes, flow polytopes, polytopes from partially ordered sets, associahedra, and generalized permutahedra.

• Günter M. Ziegler, Lectures on polytopes Vol. 152. Springer, 2012
• Matthias Beck and Sinai Robins. Computing the continuous discretely, 2nd edition, Springer, 2015. website
• Alexander Barvinok, A course in convexity, Graduate Studies in Mathematics Vol. 54

• Alexander Barvinok, Combinatorics of polytopes lecture notes, link, 2010
• Alexander Barvinok, Integer points in polyhedra, Zurich lectures in advanced mathematics, 2008.
• Alexander Barvinok, Lattice points, polyhedra, and complexity, Geometric Combinatorics, IAS/Park City Mathematics Series, 13, 2007, 19-62, link
• Alexander Barvinok, The Complexity of Generating Functions for Integer Points in Polyhedra and Beyond, Proceedings of the International Congress of Mathematicians, Madrid, August 22-30, 2006 , European Mathematical Society, vol. 3, 763-787, link
• Karola Mészáros, Root Polytopes, Triangulations, and Subdivision algebra, I, Transactions American Mathematical Society, Vol. 363, 8, 4359-4382, link
• Igor Pak, Lectures on Discrete and Polyhedral Geometry, link
• Richard P. Stanley, Enumerative Combinatorics, Volume 1, second edition, Chapter 4, link
• Richard P. Stanley, Two poset polytopes, Discrete Comput. Geom. 1:9-23 (1986), link
• Alexander Postnikov, Permutohedra, associahedra and beyond, arXiv:0507163
• Alexander Postnikov, Victor Reiner, Lauren Williams, Faces of generalized permutahedra, Documenta Mathematica (2008), Vol. 13, 207-273, link
• Günter M. Ziegler, Convex Polytopes: Extremal Constructions and $$f$$-Vector Shapes, IAS/Park City Mathematics Series Volume 14, 2004, link

### Homeworks:

There will be five bi-weekly HW during the semester accounting for 80% of the grade. You should complete the homework on your own. Some reasonable collaboration in homework is allowed. Do not hand in a solution that you did not obtain on your own or by collaboration with another student in the class. If you do collaborate with one or more students on a problem, please indicate their names.

• HW1, due Friday September 21, 2018 during class.
• HW2, due Monday October 22, 2018 during class.
• HW3, due Friday November 9, 2018 during class.
• HW4, due Monday December 3, 2018 during class.

### Final project:

The final project worth 20% of the grade where you have to read a selected paper on an additional topic and write a report of 12 page + references in LaTeX on the paper (due Thursday December 13 and give a 25 minute presentation during the final week of the semester. You can also include code related to the project.

• IPE software for creating slides for a presentation and the images. See example 1 (you can open this pdf file in IPE and edit it for your presentations). See also example of a poster.
• post from the blog of Terry Tao and links therein. And this blog post by Jordan Ellenberg.

List of topics for final project:

• Extended formulation of polytopes. Pick either 1-2 or 3.
• Michel X. Goemans. Smallest compact formulation of the permutahedron. Mathematical Programming Vol. 153, Issue 1, 2015, pp 5–11. link
• F. Barahona. On cuts and matchings in planar graphs. Mathematical Programming, 60:53–68, 1993. link
• T. Rothvoss, The matching polytope has exponential extension complexity, Journal of the ACMVolume 64 Issue 6, 2017, link
• Hirsch conjecture Pick two out of three.
• Francisco Santos, A counterexample to the Hirsch Conjecture, Annals of Mathematics Vol. 176, Issue 1, 2012, 383--412, link
• Edward D. Kim, and Francisco Santos, An update on the Hirsch conjecture, Jahresbericht der Deutschen Mathematiker-Vereinigung, Vol. 112, Issue 2, 2010, link
• F. Eisenbrand, N. Hähnle, A. Razborov and T. Rothvoss, Diameter of Polyhedra: Limits of Abstraction, 2010. SOCG'09, link
• Richard Stanley, A zonotope associated with graphical degree sequences, Applied Geometry and Discrete Combinatorics, DIMACS Series in Discrete Mathematics, Vol. 4, 1991, 555-570, link
• César Ceballos, Francisco Santos, and Günter Ziegler, Many non-equivalent realizations of the associahedron, Combinatorica, Vol. 35, Issue 5, 513--551, link (pick section 3 and one of section 4 or 5)
• César Ceballos, Arnau Padrol, Camilo Sarmiento, Dyck path triangulations and extendability, J. of Combin. Theory, Ser. A, Volume 131, 2015, 187-208, link
• Federico Ardila, Carolina Benedetti, Jeffrey Doker, Matroid Polytopes and their Volumes, Discrete & Computational Geometry, 2010, Vol. 43, Issue 4, 841--854, link
• Cara Monical, Neriman Tokcan, Alexander Yong, Newton Polytopes in Algebraic Combinatorics, link Cristian
• Karola Mészáros, Root Polytopes, Triangulations, and Subdivision algebra, I, Transactions American Mathematical Society, Vol. 363, 8, 4359-4382, link
• Paul Johnson, Lattice points and simultaneous core partitions, Electronic Journal of Combinatorics, Vol. 25, Issue 3, 2018, link GaYee
• Fu Liu, Ehrhart polynomials of cyclic polytopes, J. Combin. Theory Ser. A, Vol. 111, 1, 2005, 111--127, link
• Anastasia Chavez, Nicole Yamzon, The Dehn-Sommerville relations and the Catalan matroid, Proc. Amer. Math. Soc., Vol. 145, 2017, 4041-4047, link, Stefan
• Nan Li, Ehrhart, $$h^*$$-vectors of hypersimplices, Discrete & Computational Geometry, Vol. 48, 2012,847-878, link
• Igor Pak, Four questions on Birkhoff polytope, Annals of Combinatorics, vol. 4 (2000), 83-90, link Wilson
• Jessica Striker, The alternating sign matrix polytope, Electornic Journal of combinatorics, No. 1, 2009, link
• (variations Steinitz theorem) Circle packing: Section 1.3 from Ziegler's IAS lectures (see link above), Variational principle: Section 11.5 Pak's lecture notes (see link above).
• (a face of the Birkhoff polytope) Karola Mészáros, Alejandro Morales, Brendon Rhoades, The polytope of Tesler matrices, B. Selecta Math. New Series, Vol 23, 2007, 425 link. First two sections Jacob
• Marco Cuturi, Permanents, Transportation Polytopes and Positive Definite Kernels on Histograms, IJCAI'07 Proceedings of the 20th international joint conference on Artifical intelligence, 2007, 732-737 René

### Software

• SageMath: this is an open-source math software with a language similar to python. It includes functions for polytopes, posets, hyperplane arrangements and much more. tutorial
• CoCalc: a webpage where you can run Sage, ipython, write LaTeX documents, etc.
• LattE: software developed at UC Davis for lattice point enumeration of polytopes.
• convex package for Maple developed by Matthias Franz.
• Polymake
• Normaliz

### Course notes:

• 09/05: lec 1: Introduction
• 09/07: lec 2: Examples of polytopes

• 09/10: lec 3: Equivalence of H-representation and V-representation, the Fourier-Motzkin elimination I elimination.
• 09/12: lec 4: Equivalence of H-representation and V-representation, the Fourier-Motzkin elimination II (in the proof of Lemma 1 when we take $$x \in P(A^{\backslash k},0)$$, we can assume $$x_k=0$$ since this coordinate is free in the system. For an inductive proof of the equivalence between the H-representation and V-representation see [M] link.
• 09/14: lec 5: dual Fourier-Motzkin elimination, worksheet 1

• 09/17: lec 6: the Farkas Lemma and Carathéodory's theorem.
• 09/19: lec 7: faces of polytopes.
• 09/21: lec 8: lattice of faces of a polytope.

• 09/24: lec 9: lattice of faces of a polytope of a polytope.
• 09/26: lec 10: worksheet 2
• 09/28: lec 11: polar of a polytope

• 10/01: lec 12: polar of a polytope
• 10/03: lec 13: representation theorem of polytopes, simplicial and simple polytopes revisited.
• 10/05: lec 14: graph of a polytope I

• 10/09: lec 15: graph of a polytope II
• 10/10: lec 16: The Kalai-Kleitman bound: $$\Delta_u(d,n) \leq n^{\log_2(d)+2}$$. Bound on the diameter of the graph $$0/1$$ d-polytopes.
• 10/12: lec 17: worksheet 3

• 10/15: lec 18: faces of the permutahedron, Kalai's criterion for distinguishing a simple polytope from its graph.
• 10/17: lec 19: Balinsky's theorem: the graph of a d-polytope is d-connected.
• 10/19: lec 20: Examples of polytopes: the Birkhoff polytope.

• 10/22: lec 21: Steinitz theorem I.
• 10/24: lec 22: Ehrhart theory: motivating examples the hypercube
• 10/26: lec 23: Ehrhart theory II: triangulations of polytopes.

• 11/05: lec 28: Stanley's $$h^*$$ polynomial and coefficients of Ehrhart polynomials.
• 11/05: lec 29: Reciprocity of Ehrhart polynomials.
• 11/07: lec 30: Brion's theorem I
• 11/09: lec 31: Brion's theorem II, worksheet 5,

• 11/12: no lecture, veterans day
• 11/14: no lecture,
• 11/16: no lecture.

Thanksgiving break

• 11/26: lec 32: Brion's theorem III. Gram-Brianchon Theorem for simplices. This result holds in more generality for all polytopes.
• 11/28: lec 33: unimodular cones and sketch of Barvinok's algorithm. For more details see this paper of Barvinok and Pomersheim.
• 11/30: lec 34: $$f$$-vectors, Euler-Poincaré Theorem polytopes.

• 12/03: lec 35: Dehn-Sommerville relation for simple polytopes
• 12/05: lec 36: The Upper Bound Theorem.
• 12/08: lec 37: last lecture: examples of some interesting polytopes: order polytopes, zonotopes, hypersimplices, (generalized) permutahedra.

• 12/10: presentations: Rene, Jacob
• 12/11: presentations: Cristian, Stefan (4pm LGRT 0202)
• 12/12: presentations: GaYee, Wilson