Higher integrality conditions, volumes and Ehrhart polynomials

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. In previous work, we showed that the coefficients of the Ehrhart polynomial of a lattice-face polytope are volumes of projections of the polytope. We generalize both results by introducing a notion of k-integral polytopes, where 0-integral is equivalent to integral. We show that the Ehrhart polynomial of a k-integral polytope P has the properties that the coefficients in degrees 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.     

Résultats combinatoires sur les modules de Demazure

In this paper, we introduce the notion of polytopes with integral structure, which generalizes the notion of usual polytopes whose vertices have integral coordinates. Then we consider a symmetrizable Kac-Moody algebra. For every dominant weight λ and every element of the Weyl group w, we construct a polytope with integral structure such that its Ehrhart polynomial describes the dimension of the Demazure module of highest weight nλ associated to w.     

Counterexamples of the Conjecture on Roots of Ehrhart Polynomials

On roots of Ehrhart polynomials, Beck et al. conjecture that all roots α of the Ehrhart polynomial of an integral convex polytope of dimension d satisfy −d≤ℜ(α)≤d−1. In this paper, we provide counterexamples for this conjecture.     

Counting Lattice Points by Means of the Residue Theorem

We use the residue theorem to derive an expression for the number of lattice points in a dilated n-dimensional tetrahedron with vertices at lattice points on each coordinate axis and the origin. This expression is known as the Ehrhart polynomial. We show that it is a polynomial in t, where t is the integral dilation parameter. We prove the Ehrhart-Macdonald reciprocity law for these tetrahedra, relating the Ehrhart polynomials of the interior and the closure of the tetrahedra. To illustrate our method, we compute the Ehrhart coefficient for codimension 2. Finally, we show how our ideas can be used to compute the Ehrhart polynomial for an arbitrary convex lattice polytope.     

Computing the Ehrhart polynomial of a convex lattice polytope

We prove that computation of any fixed number of highest coefficients of the Ehrhart polynomial of an integral polytope can be reduced in polynomial time to computation of the volumes of faces. This research was supported by the United States Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University, Contract DAAL03-91-C-0027.     

Ehrhart Polynomials of 3-Dimensional Simple Integral Convex Polytopes

The author gives an explicit formula on the Ehrhart polynomial of a 3-dimensional simple integral convex polytope by using toric geometry.     

Roots of Ehrhart polynomials arising from graphs

Several polytopes arise from finite graphs. For edge and symmetric edge polytopes, in particular, exhaustive computation of the Ehrhart polynomials not merely supports the conjecture of Beck et al. that all roots α of Ehrhart polynomials of polytopes of dimension D satisfy −D≤Re(α)≤D−1, but also reveals some interesting phenomena for each type of polytope. Here we present two new conjectures: (1) the roots of the Ehrhart polynomial of an edge polytope for a complete multipartite graph of order d lie in the circle |z+\fracd4| ￡ \fracd4|z+\frac{d}{4}| \le \frac{d}{4} or are negative integers, and (2) a Gorenstein Fano polytope of dimension D has the roots of its Ehrhart polynomial in the narrower strip -\fracD2 ￡ Re(a) ￡ \fracD2-1-\frac{D}{2} \leq \mathrm{Re}(\alpha) \leq \frac{D}{2}-1. Some rigorous results to support them are obtained as well as for the original conjecture. The root distribution of Ehrhart polynomials of each type of polytope is plotted in figures.     

The Ehrhart Polynomial of the Birkhoff Polytope

The nth Birkhoff polytope is the set of all doubly stochastic n × n matrices, that is, those matrices with nonnegative real coefficients in which every row and column sums to one. A wide open problem concerns the volumes of these polytopes, which have been known for n $\leq$ 8. We present a new, complex-analytic way to compute the Ehrhart polynomial of the Birkhoff polytope, that is, the function counting the integer points in the dilated polytope. One reason to be interested in this counting function is that the leading term of the Ehrhart polynomial is—up to a trivial factor—the volume of the polytope. We implemented our methods in the form of a computer program, which yielded the Ehrhart polynomial (and hence the volume) of the ninth Birkhoff polytope, as well as the volume of the tenth Birkhoff polytope.     

A generating function for all semi-magic squares and the volume of the Birkhoff polytope

We present a multivariate generating function for all n×n nonnegative integral matrices with all row and column sums equal to a positive integer t, the so called semi-magic squares. As a consequence we obtain formulas for all coefficients of the Ehrhart polynomial of the polytope B _n of n×n doubly-stochastic matrices, also known as the Birkhoff polytope. In particular we derive formulas for the volumes of B _n and any of its faces.     

Smooth Fano Polytopes Whose Ehrhart Polynomial Has a Root with Large Real Part

The symmetric edge polytopes of odd cycles (del Pezzo polytopes) are known as smooth Fano polytopes. In this paper, we show that if the length of the cycle is 127, then the Ehrhart polynomial has a root whose real part is greater than the dimension. As a result, we have a smooth Fano polytope that is a counterexample to the two conjectures on the roots of Ehrhart polynomials.     

Computing the Ehrhart quasi-polynomial of a rational simplex

We present a polynomial time algorithm to compute any fixed number of the highest coefficients of the Ehrhart quasi-polynomial of a rational simplex. Previously such algorithms were known for integer simplices and for rational polytopes of a fixed dimension. The algorithm is based on the formula relating the th coefficient of the Ehrhart quasi-polynomial of a rational polytope to volumes of sections of the polytope by affine lattice subspaces parallel to -dimensional faces of the polytope. We discuss possible extensions and open questions.

     

Roots of Ehrhart Polynomials of Smooth Fano Polytopes

V. Golyshev conjectured that for any smooth polytope P with dim(P)≤5 the roots z∈ℂ of the Ehrhart polynomial for P have real part equal to −1/2. An elementary proof is given, and in each dimension the roots are described explicitly. We also present examples which demonstrate that this result cannot be extended to dimension six.     

Rational Ehrhart quasi-polynomials

Ehrhart?s famous theorem states that the number of integral points in a rational polytope is a quasi-polynomial in the integral dilation factor. We study the case of rational dilation factors. It turns out that the number of integral points can still be written as a rational quasi-polynomial. Furthermore, the coefficients of this rational quasi-polynomial are piecewise polynomial functions and related to each other by derivation.     

An analog of the cook theorem for polytopes

We prove that the polytope M of any combinatorial optimization problem with a linear objective function is an affine image of some facet of the cut polytope whose dimension is polynomial with respect to the dimension of M.     

Facets and volume of Gorenstein Fano polytopes

It is known that every integral convex polytope is unimodularly equivalent to a face of some Gorenstein Fano polytope. It is then reasonable to ask whether every normal polytope is unimodularly equivalent to a face of some normal Gorenstein Fano polytope. In the present paper, it is shown that, by giving new classes of normal Gorenstein Fano polytopes, each order polytope as well as each chain polytope of dimension d is unimodularly equivalent to a facet of some normal Gorenstein Fano polytopes of dimension . Furthermore, investigation on combinatorial properties, especially, Ehrhart polynomials and volume of these new polytopes will be achieved. Finally, some curious examples of Gorenstein Fano polytopes will be discovered.     

Computation of the Highest Coefficients of Weighted Ehrhart Quasi-polynomials of Rational Polyhedra

This article concerns the computational problem of counting the lattice points inside convex polytopes, when each point must be counted with a weight associated to it. We describe an efficient algorithm for computing the highest degree coefficients of the weighted Ehrhart quasi-polynomial for a rational simple polytope in varying dimension, when the weights of the lattice points are given by a polynomial function h. Our technique is based on a refinement of an algorithm of A.?Barvinok in the unweighted case (i.e., h≡1). In contrast to Barvinok’s method, our method is local, obtains an approximation on the level of generating functions, handles the general weighted case, and provides the coefficients in closed form as step polynomials of the dilation. To demonstrate the practicality of our approach, we report on computational experiments which show that even our simple implementation can compete with state-of-the-art software.     

Gelfand-Tsetlin polytopes and Feigin-Fourier-Littelmann-Vinberg polytopes as marked poset polytopes

Stanley (1986) showed how a finite partially ordered set gives rise to two polytopes, called the order polytope and chain polytope, which have the same Ehrhart polynomial despite being quite different combinatorially. We generalize his result to a wider family of polytopes constructed from a poset P with integers assigned to some of its elements.Through this construction, we explain combinatorially the relationship between the Gelfand-Tsetlin polytopes (1950) and the Feigin-Fourier-Littelmann-Vinberg polytopes (2010, 2005), which arise in the representation theory of the special linear Lie algebra. We then use the generalized Gelfand-Tsetlin polytopes of Berenstein and Zelevinsky (1989) to propose conjectural analogues of the Feigin-Fourier-Littelmann-Vinberg polytopes corresponding to the symplectic and odd orthogonal Lie algebras.     

The many aspects of counting lattice points in polytopes

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). This paper is a survey of this problem and its applications. We review the basic structure theorems about this type of counting problem. Perhaps the most famous special case is the theory of Ehrhart polynomials, introduced in the 1960s by Eugène Ehrhart. These polynomials count the number of lattice points in the different integral dilations of an integral convex polytope. We discuss recent algorithmic solutions to this problem and conclude with a look at what happens when trying to count lattice points in more complicated regions of space.     

Ehrhart Series for Connected Simple Graphs

The Ehrhart ring of the edge polytope ${\mathcal{P}_G}$ for a connected simple graph G is known to coincide with the edge ring of the same graph if G satisfies the odd cycle condition. This paper gives for a graph which does not satisfy the condition, a generating set of the defining ideal of the Ehrhart ring of the edge polytope, described by combinatorial information of the graph. From this result, two factoring properties of the Ehrhart series are obtained; the first one factors out bipartite biconnected components, and the second one factors out a even cycle which shares only one edge with other part of the graph. As an application of the factoring properties, the root distribution of Ehrhart polynomials for bipartite polygon trees is determined.     

h-Vectors of Gorenstein polytopes

We show that the Ehrhart h-vector of an integer Gorenstein polytope with a regular unimodular triangulation satisfies McMullen's g-theorem; in particular, it is unimodal. This result generalizes a recent theorem of Athanasiadis (conjectured by Stanley) for compressed polytopes. It is derived from a more general theorem on Gorenstein affine normal monoids M: one can factor K[M] (K a field) by a “long” regular sequence in such a way that the quotient is still a normal affine monoid algebra. This technique reduces all questions about the Ehrhart h-vector of P to the Ehrhart h-vector of a Gorenstein polytope Q with exactly one interior lattice point, provided each lattice point in a multiple cP, c∈N, can be written as the sum of c lattice points in P. (Up to a translation, the polytope Q belongs to the class of reflexive polytopes considered in connection with mirror symmetry.) If P has a regular unimodular triangulation, then it follows readily that the Ehrhart h-vector of P coincides with the combinatorial h-vector of the boundary complex of a simplicial polytope, and the g-theorem applies.