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.     

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.     

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.

     

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.     

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.     

Notes on the Roots of Ehrhart Polynomials

We determine lattice polytopes of smallest volume with a given number of interior lattice points. We show that the Ehrhart polynomials of those with one interior lattice point have largest roots with norm of order n², where n is the dimension. This improves on the previously best known bound n and complements a recent result of Braun where it is shown that the norm of a root of a Ehrhart polynomial is at most of order n². For the class of 0-symmetric lattice polytopes we present a conjecture on the smallest volume for a given number of interior lattice points and prove the conjecture for crosspolytopes. We further give a characterisation of the roots of Ehrhart polyomials in the three-dimensional case and we classify for n ≤ 4 all lattice polytopes whose roots of their Ehrhart polynomials have all real part -1/2. These polytopes belong to the class of reflexive polytopes.     

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.     

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.     

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.     

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.     

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.     

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.     

Inside-out polytopes

We present a common generalization of counting lattice points in rational polytopes and the enumeration of proper graph colorings, nowhere-zero flows on graphs, magic squares and graphs, antimagic squares and graphs, compositions of an integer whose parts are partially distinct, and generalized latin squares. Our method is to generalize Ehrhart's theory of lattice-point counting to a convex polytope dissected by a hyperplane arrangement. We particularly develop the applications to graph and signed-graph coloring, compositions of an integer, and antimagic labellings.     

The Mixed Degree of Families of Lattice Polytopes

Annals of Combinatorics - The degree of a lattice polytope is a notion in Ehrhart theory that was studied quite intensively over previous years. It is well known that a lattice polytope has...     

Residue formulae, vector partition functions and lattice points in rational polytopes

We obtain residue formulae for certain functions of several variables. As an application, we obtain closed formulae for vector partition functions and for their continuous analogs. They imply an Euler-MacLaurin summation formula for vector partition functions, and for rational convex polytopes as well: we express the sum of values of a polynomial function at all lattice points of a rational convex polytope in terms of the variation of the integral of the function over the deformed polytope.

     

The Partial-Fractions Method for Counting Solutions to Integral Linear Systems

We present a new tool to compute the number $\phi_{\bf A} (b)$ of integer solutions to the linear system $$ x \geq 0, A x = b, $$ where the coefficients of $A$ and $b$ are integral. $\phi_{\bf A} (b)$ is often described as a vector partition function. Our methods use partial fraction expansions of Eulers generating function for $\phi_{\bf A} (\b)$. A special class of vector partition functions are Ehrhart (quasi-)polynomials counting integer points in dilated polytopes.     

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.     

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.     

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.