Ehrhart polynomials of cyclic polytopes

The Ehrhart polynomial of an integral convex polytope counts the number of lattice points in dilates of the polytope. In (Coefficients and roots of Ehrhart polynomials, preprint), the authors conjectured that for any cyclic polytope with integral parameters, the Ehrhart polynomial of it is equal to its volume plus the Ehrhart polynomial of its lower envelope and proved the case when the dimension d=2. In our article, we prove the conjecture for any dimension.     

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.     

Lattice polytopes of degree 2

A theorem of Scott gives an upper bound for the normalized volume of lattice polygons with exactly i>0 interior lattice points. We will show that the same bound is true for the normalized volume of lattice polytopes of degree 2 even in higher dimensions. In particular, there is only a finite number of quadratic polynomials with fixed leading coefficient being the h^∗-polynomial of a lattice polytope.     

Ehrhart Polynomials of Matroid Polytopes and Polymatroids

We investigate properties of Ehrhart polynomials for matroid polytopes, independence matroid polytopes, and polymatroids. In the first half of the paper we prove that, for fixed rank, Ehrhart polynomials of matroid polytopes and polymatroids are computable in polynomial time. The proof relies on the geometry of these polytopes as well as a new refined analysis of the evaluation of Todd polynomials. In the second half we discuss two conjectures about the h ^*-vector and the coefficients of Ehrhart polynomials of matroid polytopes; we provide theoretical and computational evidence for their validity.     

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.     

Notes on lattice points of zonotopes and lattice-face polytopes

Minkowski’s second theorem on successive minima gives an upper bound on the volume of a convex body in terms of its successive minima. We study the problem to generalize Minkowski’s bound by replacing the volume by the lattice point enumerator of a convex body. In this context we are interested in bounds on the coefficients of Ehrhart polynomials of lattice polytopes via the successive minima. Our results for lattice zonotopes and lattice-face polytopes imply, in particular, that for 0-symmetric lattice-face polytopes and lattice parallelepipeds the volume can be replaced by the lattice point enumerator.     

Special simplices and Gorenstein toric rings

Athanasiadis [Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley, J. Reine Angew. Math., to appear.] studies an effective technique to show that Gorenstein sequences coming from compressed polytopes are unimodal. In the present paper we will use such the technique to find a rich class of Gorenstein toric rings with unimodal h-vectors arising from finite graphs.     

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.     

Ehrhart polynomials of lattice-face polytopes

There is a simple formula for the Ehrhart polynomial of a cyclic polytope. The purpose of this paper is to show that the same formula holds for a more general class of polytopes, lattice-face polytopes. We develop a way of decomposing any -dimensional simplex in general position into signed sets, each of which corresponds to a permutation in the symmetric group and reduce the problem of counting lattice points in a polytope in general position to that of counting lattice points in these special signed sets. Applying this decomposition to a lattice-face simplex, we obtain signed sets with special properties that allow us to count the number of lattice points inside them. We are thus able to conclude the desired formula for the Ehrhart polynomials of lattice-face polytopes.

     

Equivariant Ehrhart theory

Motivated by representation theory and geometry, we introduce and develop an equivariant generalization of Ehrhart theory, the study of lattice points in dilations of lattice polytopes. We prove representation-theoretic analogues of numerous classical results, and give applications to the Ehrhart theory of rational polytopes and centrally symmetric polytopes. We also recover a character formula of Procesi, Dolgachev, Lunts and Stembridge for the action of a Weyl group on the cohomology of a toric variety associated to a root system.     

Norm Bounds for Ehrhart Polynomial Roots

M. Beck et al. found that the roots of the Ehrhart polynomial of a d-dimensional lattice polytope are bounded above in norm by 1+(d+1)!. We provide an improved bound which is quadratic in d and applies to a larger family of polynomials.     

Simple polytopes without small separators

We show that by cutting off the vertices and then the edges of neighborly cubical polytopes, one obtains simple 4-dimensional polytopes with n vertices such that all separators of the graph have size at least Ω(n/log^3/2 n). This disproves a conjecture by Kalai from 1991/2004.     

Ehrhart polynomials and stringy Betti numbers

We study the connection between stringy Betti numbers of Gorenstein toric varieties and the generating functions of the Ehrhart polynomials of certain polyhedral regions. We use this point of view to give counterexamples to Hibi's conjecture on the unimodality of δ-vectors of reflexive polytopes. The first author was partially supported by NSF grant DMS 0500127 and the second author was supported by a Graduate Research Fellowship from the NSF     

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.     

Unimodality Questions for Integrally Closed Lattice Polytopes

It is a famous open question whether every integrally closed reflexive polytope has a unimodal Ehrhart δ -vector. We generalize this question to arbitrary integrally closed lattice polytopes and we prove unimodality for the δ -vector of lattice parallelepipeds. This is the first nontrivial class of integrally closed polytopes. Moreover, we suggest a new approach to the problem for reflexive polytopes via triangulations.     

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.     

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 h ?-Vectors of Hypersimplices

We consider the Ehrhart h ^?-vector for the hypersimplex. It is well-known that the sum of the $h_{i}^{*}$ is the normalized volume which equals the Eulerian numbers. The main result is a proof of a conjecture by R.?Stanley which gives an interpretation of the $h^{*}_{i}$ coefficients in terms of descents and exceedances. Our proof is geometric using a careful book-keeping of a shelling of a unimodular triangulation. We generalize this result to other closely related polytopes.     

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.     

Bounds on the coefficients of tension and flow polynomials

The goal of this article is to obtain bounds on the coefficients of modular and integral flow and tension polynomials of graphs. To this end we use the fact that these polynomials can be realized as Ehrhart polynomials of inside-out polytopes. Inside-out polytopes come with an associated relative polytopal complex and, for a wide class of inside-out polytopes, we show that this complex has a convex ear decomposition. This leads to the desired bounds on the coefficients of these polynomials.