Current homework: Beck Haase
List of participants
Subject
Format
Organizers
Audience
Schedule & events
Practical hints
Sponsors
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
ABSTRACT:
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.
Kreweras' conjecture asserts that any perfect matching of the hypercube Qd (d >= 2) can be extended to a Hamiltonian cycle. We proved this conjecture. The proof is very nice and elegant and I will present it.
For given $k,n\in {1,2,...}$, a $k$-triangulation of the convex
$n$-gon is a maximal set of diagonals in it such that no
$k+1$ of them intersect.
There are several nice facts about $k$-triangulations (some old, some
new) that generalize nicely what is known for triangulations. Among
them:
1) all the $k$-triangulations of an $n$-gon have the same number of
edges, namely $2kn-{2k+1 \choose 2}$.
2) every edge of a $k$-triangulation (of length at least $k+1$,
measured in terms of vertices of the $n$-gon) can be flipped in a
unique way: after its removal there is a only one edge that can be
introduced to get a new $k$-triangulation.
Of course, properties 1 and 2 say that there is a graph of
$k$-triangulations, which is regular of degree $kn-{2k+1 \choose 2}$
(note, the $kn$ edges of length at most $k$ are present in every
$k$-triangulation and are irrelevant for this graph. They play the
role of boundary edges in $k$ triangulations. There is the
conjecture that this graph is the skeleton of a simple
polytope, but this has not been proved (Jakob Jonnson proved
that it is the dual graph of a shellable simplicial sphere of
the appropriate dimension, but not that this sphere is polytopal).
Tuesday | 9-12 | in room 25/26 |
Tuesday | 2-4 | in room 09 |
Wednesday | 9-12 | in room 07/08 |
Wednesday | 2-4 | in room 09 |
Tuesday | 8-9 | in room 33 |
Wednesday | 8-9 | in room 33 |
Date | Breakfast Master | Date | Breakfast Master |
May 8 | Christian | May 9 | Christian |
May 15 | Vincent | May 16 | Piotr |
May 22 | Jan | ||
May 29 | Kathrin | May 30 | Felix |
June 5 | Hossein | June 6 | Jirka |
June 12 | Holger | June 13 | Kord |
June 19 | Aaron, Steven | June 20 | Vinh |
June 26 | Bruno | June 27 | Ronald |
July 3 | Jan | July 4 | Piotr |
July 10 | Kort | July 11 | Miriam |
July 17 | Jirka, Yury | July 18 | Steven |
July 24 | Christine | July 25 | Aaron |
Sponsors: The (Pre)Doc Course is supported by