Lattice Point Enumeration | March 25 - 27, 2010
Richard Stanley | MIT
A Survey of Integer Points in Polytopes
Abstract
The problem of counting the number of integer points in a convex polytope with integer vertices (or in more general polyhedral regions) has a long history going back to Georg Alexander Pick (1859 - 1942). Pick's classic theorem asserts that if a lattice polygon P in the plane has I lattice points in its interior and B points on its boundary, then the area A of P is given by A = (2I+B-2)/2. Attempts to generalize this result to higher dimensions have led to much interaction between geometry and combinatorics, with unexpected connections to topology, commutative algebra, algebraic geometry, computer science, and other areas. We will survey some of the highlights of this subject.
Descent Polytopes, Minkowski Sums, and Gneralized Permutohedra
Abstract
The Ehrhart polynomial i(P,n) of an integer polytope counts the number of integer points in the dilate nP, n>0. In the second and third lectures we give examples of polytopes with interesting volumes or Ehrhart polynomials. The second lecture will concern the descent polytopes of D. Chebikin and R. Ehrenborg and some polytopes expressible as Minkowski sums, especially the generalized permutohedra of A. Postnikov.
Root polytopes, subdivision algebras, and matching polytopes
Abstract
We continue with examples of polytopes with interesting volumes or Ehrhart polynomials. We discuss the work of K. Meszaros relating root polytopes, flow polytopes, subdivision algebras, and Yang-Baxter algebras. We finish with the work of R. Liu on certain matching polytopes and their connection with Specht modules.
Christos A. Athanasiadis | Department of Mathematics, University of Athens, Greece
Magic Squares, Lattice Points and Ehrhart Polynomials
Abstract
Magic squares are square matrices with non-negative integer entries which have all their row sums and column sums equal to each other. The enumeration of n by n magic squares with a given row sum is one of the combinatorial problems which provided the main motivation for the development of modern combinatorial commutative algebra. After the connection to lattice point enumeration is explained, this lecture will servey some of the main results, recent progress and open questions associated to this problem, and will discuss extentions to the enumeration of lattice points in polyhedra in more general situations.
Jesus De Loera | Department of Mathematics, UC Davis
Advances in Computer-based Enumeration of Lattice Points
Abstract
I will begin by reviewing the known algorithms for counting lattice points inside polyhedra and computing Ehrhart quasi-polynomials. Then I will present two new algorithmic results (and associated software).
1) Normally lattice points are counted each with "weight" 1. But if each lattice point $\alpha$ in the polytope $P$ is counted with a "polynomial weight" $f(\alpha)$ there is a generalization of Ehrhart quasipolynomials. The leading coefficient is not a volume anymore, but the integral of $f$ over $P$. In joint work with Baldoni, Berline, Koeppe, and Vergne, we settled the computational complexity of the problem of integrating a polynomial function $f$ over a rational simplex. We prove that the problem is $NP$-hard for arbitrary polynomials via a generalization of a theorem of Motzkin and Straus. On the other hand, if the polynomial depends only on a fixed number of variables, while its degree and the dimension of the simplex are allowed to vary, we prove that symbolic integration can be done in polynomial time. As a consequence, for polynomials of fixed total degree, there is a polynomial time algorithm as well. Our symbolic algorithms are very fast in practice, rivaling even numeric quadrature code.
2) Since exact counting is $\#P$-hard it is not surprising that there is a rich and exciting theory of \emph{estimation and approximation}. There are various estimating algorithms, e.g. Monte-Carlo sampling, Markov-Chain Monte-Carlo, and others. Sadly, many of these available methods are only suitable for special polytopes or make the impractical assumption that finding a first lattice point is easy. For general polytopes even deciding whether a lattice point lies inside is an NP-hard, a tough challenge emerges.
We report our experimental investigations with a recent method developed by A. Barvinok and J. Hartigan. The method computes estimations on the number of lattice points inside an arbitrary polyhedron by solving specially constructed convex optimization problems on polytopes. Unlike other techniques the Barvinok Hartigan idea uses no prior knowledge about the input polyhedron and the procedure is deterministic (with probabilistic estimates) and runs in polynomial time.
Fu Liu | Department of Mathematics, UC Davis
Higher Integrality Conditions and Volumes of Slices
Abstract
A polytope is integral if all of its vertices are lattice points. The constant term of the Ehrhart polynomial of an integral polytope is known to be 1. I generalize this result by introducing the definition of k-integral polytopes, where 0-integral is equivalent to integral. I will show that the Ehrhart polynomial of a k-integral polytope P has the properties that the coefficients in degrees of less than or equal to k are determined by a projection of P, and the coefficients in higher degrees are determined by slices of P. A key step of the proof is that under certain generality conditions, the volume of a polytope is equal to the sum of volumes of slices of the polytope.
Matthias Beck | Department of Mathematics, San Francisco State University
Combinatorial Reciprocity Theorems
Abstract
A common theme of enumerative combinatorics are counting functions given by polynomials that are evaluated at positive integers. For example, one proves in any introductory graph theory course that the number of proper k-colorings of a given graph G is a polynomial in k, the "chromatic polynomial" of G. Combinatorial reciprocity theorems give interpretations of these polynomials at negative integers. For example, when we evaluate the chromatic polynomial of G at -1, we obtain (up to a sign) the number of acyclic orientations of G, that is, those orientations of G that do not contain a coherent cycle (a theorem of R. Stanley).
Combinatorics is abundant with polynomials that count something when evaluated at positive integers, and many of these polynomials have a completely different interpretation when evaluated at negative integers. We follow a common thread of chromatic and flow polynomials of graphs and signed graphs, Ehrhart polynomials enumerating integer points in polytopes, and characteristic polynomials of hyperplane arrangements.
Sinai Robins | Department of Mathematics, Nanyang Technological University, Singapore
Tiling Rd with polytopes
Abstract
We say that a polytope P tiles Rd with multiplicity k if there is a set of translations L such that each point in Rd gets covered exactly k times under this set of traslations. When k=1, this condition is the usual tiling condition under Euclidean translations. We prove that if a lattice polytope P satisfies some algebraically defined conditions, then P multiply tiles Rd. Moreover, we give an algorithm to compute the set of translations L, in the case when L is a single lattice of translations.
Takayuki Hibi | Department of Mathematics, Osaka University, Japan
Roots of Ehrhart Polynomials of Gorenstein Fano Polytopes
Abstract
Given arbitrary integers $k$ and $d$ with $0 ¥leq 2k ¥leq d$, we construct a Gorenstein Fano polytope ${¥mathcal P} ¥subset {¥bf R}^d$ of dimension $d$ such that (i) its Ehrhart polynomial $i({¥mathcal P}, n)$ possesses $d$ distinct roots; (ii) $i({¥mathcal P}, n)$ possesses exactly $2k$ imaginary roots; (iii) i({¥mathcal P}, n)$ possesses exactly $d - 2k$ real roots; (iv) the real part of each of the imaginary roots is equal to $- 1 / 2$; (v) all of the real roots belong to the open interval $(-1, 0)$. This is a joint work with Akihiro Higashitani and Hidefumi Ohsugi.
