Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

(Pre)Doc Course:
Integer Points in Polyhedra

May 8 - July 25, 2007
Freie Universitšt Berlin

Current homework: Beck   Haase

List of participants

Schedule & events
Practical hints


Subject: "A wide variety of topics in pure and applied mathematics involve the problem of counting the number of lattice points inside a convex bounded polyhedron, for short called a polytope. Applications range from the very pure (number theory, toric Hilbert functions, Kostant's partition function in representation theory) to the most applied (cryptography, integer programming, contingency tables)."*
* from: Jesķs de Loera The Many Aspects of Counting Lattice Points in Polytopes.


Format: The course will be subdivided into four mini-courses held by four lecturers. These mini-courses will treat different aspects of integer points in polyhedra. They will give an introduction to the basic structure theorems and algorithms, as well as the various methods that are employed in their study. Selected applications - within mathematics and beyond - will be discussed.

Rekha Thomas (Seattle)
May 8-22
Integer hulls of rational polyhedra

ABSTRACT: The main focus of the first three weeks will be on the convex hull of integer points in a rational polyhedron. This object is again a polyhedron and is known as the integer hull of the rational polyhedron. Integer hulls play a fundamental role in integer programming and have been studied extensively. Yet many open questions remain. In these lectures we will approach integer hulls from the point of view of optimization. We will spend roughly half the time on understanding the structure of integer hulls and algorithms for computing them. The other half will focus on the complexity of these objects in terms of the size of the original rational polyhedron. No knowledge of polyhedral or complexity theory will be assumed. We will develop the necessary basics in the first week and during the course of the lectures, as needed.
MAIN REFERENCE: Theory of Linear and Integer Programming, Alexander Schrijver, Wiley-Interscience Series in Discrete Mathematics, 1986.

Raymond Hemmecke (Magdeburg)
May 29-June 13
Representations of lattice point sets

MAIN REFERENCE: Part I: Integral bases, Hilbert bases, and Graver bases in Representations of lattice point sets -- Theory, Algorithms, Applications; Raymond Hemmecke, 2006.

Matthias Beck (San Francisco)
June 19-July 11
Computing the continuous discretely

ABSTRACT: We use generating functions to count integer ("lattice") points in polytopes with rational vertices. More precisely, we study the number of lattice points as the polytope gets dilated by an integer factor. This expression is known as the Ehrhart quasipolynomial and we think of it as the discrete volume of the polytope.
Because polytopes can be described by a system of linear equalities and inequalities, they appear in a wealth of areas. We will show applications of Ehrhart quasipolynomials to number theory, combinatorics, and computational geometry.
I plan to cover most of the material in my book with Sinai Robins (see below). We place a strong emphasis on computational techniques, and on computing volumes by counting integer points using various old and new ideas. Thus, the formulas we get should not only be pretty (which they are!) but should also allow us to efficiently compute volumes by using some nice functions.
MAIN REFERENCE: Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra; Matthias Beck and Sinai Robins; Springer UTM 2007.

Christian Haase (Berlin)
July 17-25
Geometry of numbers and flatness

ABSTRACT: Geometry of numbers was developed by Minkowski with number theoretic applications in mind. Minkowski's first theorem gives a volume bound for convex bodies which are centrally symmetric about the origin, and which do not contain non-zero lattice points. The volume of convex bodies which do not contain any lattice points at all cannot be bounded. Yet, they have to be flat in at least one direction.
This year we are celebrating the 25th anniversary of the LLL algorithm which started the development of an algorithmic theory of numbers. It has found applications to the factorization of polynomials, integer programming, cryptography, and more.
MAIN REFERENCE: A Course in Convexity; Alexander Barvinok; AMS 2002.

The language of the program is English.


Schedule & events:

The current plan has lectures and exercise sessions essentially all day Tuesdays and Wednesdays. This material should keep you occupied for a good portion of the rest of the week. Nevertheless, there should be ample time for mathematical as well as non-mathematical activities.
In terms of a mathematical program, there are two talks every Monday afternoon, hosted by the research training group. Then, there are the BMS Fridays, and last but not least, there are all the regular courses offered by the three Berlin universities.
In terms of a non-mathematical program, we hope that, as students get to know each other, they will organize activities themselves. Of course we are happy to help or to suggest things to do in Berlin and around.


Practical hints:

This is the place where you find hints on how to find reasonably priced accomodation, how to get around Berlin, and the like. If there is anything missing, PLEASE let us know. (Most of the links lead to German pages, sorry.)


Sponsors: The (Pre)Doc Course is supported by