Integer Polyhedra
Summer Semester 2009
Announcements
Meeting times We have agreed on new meeting times: Tuesdays 10:05-11:35 & 12:30-14:00.

The second additional class will be an exercise session on tuesday, May 19.
Topics
This course presents the theory of integer or lattice polytopes: convex polytopes whose vertices have integer coordinates. They appear in various fields of mathematics.

The main part of the course deals with characteristic properties of these polytopes. We discuss relations between (numbers of) lattice points in the interior, the boundary, and dilates of such polytopes. We will prove that the number of lattice points in the k-th dilate is given by a polynomial (Ehrhart's Theorem). The coefficients of this and similar polynomials encode various combinatorial and geometric properties of the polytope.

We will also discuss applications of lattice polytopes in different fields of mathematics, e.g.:

Commutative algebra and algebraic geometry: Any integer point in n-space defines a monomial in n variables. Relations among integer points in a polytope define toric ideals and toric varieties.

Integer linear programming: To find an integer point in a polytope that maximizes some linear functional we can study certain generating sets of the associated toric ideal. These define test sets that we can use to improve a given feasible solution.
Times
  • Class: Tuesday 10:05 - 11:35, SR 25/26 (Arnimallee 6)
  • Class/Tutorial: Tuesday 12:30 - 14:00, SR 211 (Arnimallee 3)
  • Seminar: Wednesday 10:15 - 11:45, SR 211 (Arnimallee 3)
Office Hours
during term: Tue 16 - 17, otherwise by appointment
(Room 103, Arnimallee 3).

Benjamin Nill
n.V.
(Room 103, Arnimallee 3).

Christian Haase
n.V.
(Room 201, Arnimallee 3).

Course Contents
class date Contents
Notes last modified
04/14 Basics
lattices
Hilbert bases
subdivisions abd triangulations
04/21 Shellings and Euler characteristic
Ehrhart Theory
generating functions
examples
integer point generating function and series
Ehrhart's theorem
04/28 no class
05/05 Ehrhart's theorem
h*-polynomial
degree and codegree, normalized volume
Stanley's reciprocity theorem
Ehrhart reciprocity
05/12 Ehrhart reciprocity
Stanley's nonnegativity theorem
Brianchon-Gram identity
Brion's theorem
signed decompositions of simplicial cones
05/19 signed decompositions of simplicial cones
Barvinok's algorithm
Geometry of Numbers
Blichfeldt's theorem
Minkowski's first theorem
05/26
06/02
06/09
06/16
06/23 Unimodular triangulations
pulling subdivisions
regular full triangulations exist
unimodular triangulations don't
Paco's Lemma
06/30 applications of Paco's Lemma
Knudsen-Mumford-Waterman Theorem
07/07 Gorenstein polytopes with RUT have unimodal h* vector
07/14
Seminar Schedule
We have collected a list of potential topics that can be presented in the seminar. The order given here is not fixed.
You may of course also propose your own topic, or ask us for more suggestions.
date Title
speaker references
04/15 polygons and the number 12 Benjamin [PR]
04/22 polygons and onion skins Therese [HS]
05/06 lattice width Matthias [HZ]
05/13 Gröbner bases, Graver bases and integer programming Benjamin [AWW]
05/20 Roots of Ehrhart polynomials Marianne
05/27 applications of Minkowski's theorems Moritz [B1], Ch. VII.4
06/03 Short vectors in lattices: LLL and PSLQ Moritz [B2], Ch. 12 & [PSLQ]
06/10 Fourier series and periodic functions on Z Felix [BR], Ch. 7
06/17 Dedekind sums Felix [BR], Ch. 8
06/24 integer Carathéodory Kaie [BGHMW] & [Seb]
07/01 unimodular triangulations of 3-polytopes Kaie [KS]
07/08 Algorithms to compute Hilbert bases Lars [H]
07/15 What I did this summer Benjamin
Exercises
date Contents
due
04/14 lattices and shellings 04/21
04/21 Ehrhart polynomials 05/05
05/05 Ehrhart polynomials II 05/12
05/12 Reciprocity 05/19
05/19 Minkowski 05/26
05/26 Lattices 06/02
06/02 Width 06/09
06/09 Finiteness Theorem 06/16
06/16 Gorenstein and Reflexive Polytopes 06/23
06/23 Unimodular Triangulations, Pulling
06/30 Unimodular Triangulations, Facet Width One
07/07
07/14
Literature
We have reserved some books in the library. They can be found in the shelf next to the door leading to the journal room (turn right after the front desk).
 
Text Books
[AZ] Aigner, Martin; Ziegler, Günter: Proofs from THE BOOK. Springer-Verlag, Berlin. viii+199. (1998). [3-540-63698-6]
[B1] Barvinok, Alexander: A course in convexity. Graduate Studies in Mathematics. 54. Providence, RI: American Mathematical Society (AMS). x, 366 p. (2002). [ISBN 0-8218-2968-8/hbk; ISSN 1065-7339]
[B2] Barvinok, Alexander: Integer Points in Polyhedra. Zurich Lectures in Advanced Mathematics. European Mathematical Society (EMS), 2008.
[BG] Bruns, Winfried; Gubeladze Joseph: Polytopes, Rings, and K-Theory. Springer to appear 2009.
[BR] Beck, Matthias; Robins, Sinai: Computing the continuous discretely. Integer-point enumeration in polyhedra. Springer Undergraduate Texts in Mathematics, to appear.
[H] Hemmecke, Raymond: Representations of lattice point sets: Theory, Algorithms, Applications. Habilitation thesis, University Magdeburg, 2006.
[Sch1] Schrijver, Alexander: Theory of linear and integer programming. Repr. Chichester: Wiley. xi, 471 p. (1998). [ISBN 0-471-98232-6/pbk]
[Sch2] Schrijver, Alexander: Combinatorial Optimization. Polyhedra and Efficiency. Repr. Springer
[Stu] Sturmfels, Bernd: Gröbner bases and convex polytopes. University Lecture Series. 8. Providece, RI: American Mathematical Society (AMS). xi, 162 p. (1996). [ISBN 0-8218-0487-1]
[Zie] Ziegler, Günter, Lectures on Polytopes, Springer
 
Journal Articles
[AWW] Aardal, Karen; Weismantel, Robert; Wolsey, Laurence: Non-standard approaches to integer programming. Discrete Applied Mathematics 123 (2002) 5 ­ 74 [PDF]
[BGHMW] Bruns, Winfried; Gubeladze, Joseph; Henk, Martin; Martin, Alexander; Weismantel, Robert: A Counterexample to an Integer Analogue of Carathéodory's Theorem J. Reine Angew. Math. 510 (1999), 179-185 [PDF]
[PSLQ] Ferguson, Helaman; Bailey, David; Arno, Stephen: Analysis of PSLQ, An Integer Relation Finding Algorithm. Math. Comput. 68, 351-369, 1999.
[HM] Haase, Christian; Ilarion Melnikov: The reflexive dimension of a lattice polytope. Annals of Combinatorics, 10:211-217, 2006. [PDF]
[HS] Haase, Christian; Schicho, Josef: Lattice Polygons and the number 2i+7. Am. Math. Mon. February 2009. math.CO/0406224
[HZ] Haase, Christian; Ziegler, Günter: On the maximal width of empty lattice simplices. European J. Combinatorics , 21(1):111-119, 2000. [PDF]
[KS] Kantor, Jean-Michel; Sarkaria, Karanbir: On primitive subdivisions of an elementary tetrahedron Pacific J. Math. 211 (2003), 123-155 PJM
[PR] Poonen, Bjorn; Rodriguez-Villegas, Fernando: Lattice polygons and the number 12. Am. Math. Mon. 107, No.3, 238-250 (2000) [PS]
[Sca] Scarf, Herbert: Integral polyhedra in three space. Math. Oper. Res. 10 (3) 403-438 (1985). [ISSN 0364-765X]
[Seb] András Sebö: Hilbert bases, Carathéodory's Theorem and Combinatorial Optimization in Ravindran Kannan and William R. Pulleyblank (eds.) Integer Programming and Combinatorial Optimization Math. Prog. Soc., Univ. Waterloo Press 1990, 431-456 [PS]
[Ver] R. Vershynin Integer Cells in Convex Sets. math.FA/0403278
Prerequisites
Formally, this course is a continuation of Discrete Mathematics II, however, the course is clearly accessible also to students that have not attended this course.

We will assume some basic familarity with the theory of convex polytopes.
Examinations
To get the ECTS points it is necessary to
  • regulary attend the tutorial and the seminar (this usually means to miss at most two)
  • hand in essentialy correct solutions to at least 50% of the assigned homework. You should be able to present your solution in the tutorial.
  • give a talk in the seminar.
  • pass the exam at the end of the semester.
Your final mark depends on your result in the exam and on the presentation in the seminar (if you only attend the seminar, or only the lecture, then of course, only this counts...).