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.
Main Reading Sources:
- 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
Other Reading Sources and links:
- 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.
Resources for your presentation
- 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
Links:
- Discrete
math seminar at UMass, see past talks here.
- website of course by Günter Ziegler on
3-polytopes, June 2018
- ipe: drawing editor for
pdf, eps images. You can enter LaTeX on the images. You can also do
entire slide presentations in it.
.