Integer Polyhedra
Summer Semester 2009
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.
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).
(Room 103, Arnimallee 3).
Benjamin Nill
n.V.
(Room 103, Arnimallee 3).
(Room 103, Arnimallee 3).
Christian Haase
n.V.
(Room 201, Arnimallee 3).
(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.
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.
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.