Research Group Lattice Polytopes

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.

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.

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

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

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

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

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

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.

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