On the facets of the secondary polytope

The secondary polytope of a point configuration A is a polytope whose face poset is isomorphic to the poset of all regular subdivisions of A. While the vertices of the secondary polytope - corresponding to the triangulations of A - are very well studied, there is not much known about the facets of the secondary polytope.The splits of a polytope, subdivisions with exactly two maximal faces, are the simplest examples of such facets and the first that were systematically investigated. The present paper can be seen as a continuation of these studies and as a starting point of an examination of the subdivisions corresponding to the facets of the secondary polytope in general. As a special case, the notion of k-split is introduced as a possibility to classify polytopes in accordance to the complexity of the facets of their secondary polytopes. An application to matroid subdivisions of hypersimplices and tropical geometry is given.     

Extensions of regular polytopes with preassigned Schläfli symbol

We say that a (d+1)-polytope P is an extension of a polytope K if the facets or the vertex figures of P are isomorphic to K. The Schläfli symbol of any regular extension of a regular polytope is determined except for its first or last entry. For any regular polytope K we construct regular extensions with any even number as first entry of the Schläfli symbol. These extensions are lattices if K is a lattice. Moreover, using the so-called CPR graphs we provide a more general way of constructing extensions of polytopes.     

Flow polytopes and the graph of reflexive polytopes

We suggest defining the structure of an unoriented graph R_d on the set of reflexive polytopes of a fixed dimension d. The edges are induced by easy mutations of the polytopes to create the possibility of walks along connected components inside this graph. For this, we consider two types of mutations: Those provided by performing duality via nef-partitions, and those arising from varying the lattice. Then for d≤3, we identify the flow polytopes among the reflexive polytopes of each single component of the graph R_d. For this, we present for any dimension d≥2 an explicit finite list of quivers giving all d-dimensional reflexive flow polytopes up to lattice isomorphism. We deduce as an application that any such polytope has at most 6(d−1) facets.     

Gorenstein polytopes and their stringy E-functions

Inspired by ideas from algebraic geometry, Batyrev and the first named author have introduced the stringy E-function of a Gorenstein polytope. We prove that this a priori rational function is actually a polynomial, which is part of a conjecture of Batyrev and the first named author. The proof relies on a comparison result for the lattice point structure of a Gorenstein polytope P, a face F of P and the face of the dual Gorenstein polytope corresponding to F. In addition, we study joins of Gorenstein polytopes and introduce the notion of an irreducible Gorenstein polytope. We show how these concepts relate to the decomposition of nef-partitions.     

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.     

Translational tilings by a polytope, with multiplicity

We study the problem of covering ? ^d by overlapping translates of a convex polytope, such that almost every point of ? ^d is covered exactly k times. Such a covering of Euclidean space by a discrete set of translations is called a k-tiling. The investigation of simple tilings by translations (which we call 1-tilings in this context) began with the work of Fedorov [5] and Minkowski [15], and was later extended by Venkov and McMullen to give a complete characterization of all convex objects that 1-tile ? ^d . By contrast, for k ≥2, the collection of polytopes that k-tile is much wider than the collection of polytopes that 1-tile, and there is currently no known analogous characterization for the polytopes that k-tile. Here we first give the necessary conditions for polytopes P that k-tile, by proving that if P k-tiles ? ^d by translations, then it is centrally symmetric, and its facets are also centrally symmetric. These are the analogues of Minkowski’s conditions for 1-tiling polytopes, but it turns out that very new methods are necessary for the development of the theory. In the case that P has rational vertices, we also prove that the converse is true; that is, if P is a rational polytope, is centrally symmetric, and has centrally symmetric facets, then P must k-tile ? ^d for some positive integer k.     

Flag enumerations of matroid base polytopes

In this paper, we study flag structures of matroid base polytopes. We describe faces of matroid base polytopes in terms of matroid data, and give conditions for hyperplane splits of matroid base polytopes. Also, we show how the cd-index of a polytope can be expressed when a polytope is split by a hyperplane, and apply these to the cd-index of a matroid base polytope of a rank 2 matroid.     

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.     

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.     

Minkowski Length of 3D Lattice Polytopes

We study the Minkowski length L(P) of a lattice polytope P, which is defined to be the largest number of non-trivial primitive segments whose Minkowski sum lies in P. The Minkowski length represents the largest possible number of factors in a factorization of polynomials with exponent vectors in P, and shows up in lower bounds for the minimum distance of toric codes. In this paper we give a polytime algorithm for computing L(P) where P is a 3D lattice polytope. We next study 3D lattice polytopes of Minkowski length 1. In particular, we show that if Q, a subpolytope of P, is the Minkowski sum of L=L(P) lattice polytopes Q _i , each of Minkowski length 1, then the total number of interior lattice points of the polytopes Q ₁,??,Q _L is at most 4. Both results extend previously known results for lattice polygons. Our methods differ substantially from those used in the two-dimensional case.     

Dynamique de la diffusion de l'erreur sur plusieurs polytopes

We discuss algorithms for scheduling, greedy for the Euclidean norm, with inputs in a family of polytopes lying in an affine space and the corresponding outputs chosen among the vertices of the respective polytopes. Such scheduling problems arise in various settings. We provide simple examples where the error remains bounded, including cases when there are infinitely many polytopes. In the case of a single polytope the boundedness of the cumulative error is known to be equivalent to the existence of an invariant region for a dynamical system in the affine space that contains this polytope. We show here that, on the contrary, no bounded invariant region can be found in affine space in general, as soon as there are at least two different polytopes. To cite this article: C. Tresser, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

On the variance of random polytopes

A random polytope is the convex hull of uniformly distributed random points in a convex body K. A general lower bound on the variance of the volume and f-vector of random polytopes is proved. Also an upper bound in the case when K is a polytope is given. For polytopes, as for smooth convex bodies, the upper and lower bounds are of the same order of magnitude. The results imply a law of large numbers for the volume and f-vector of random polytopes when K is a polytope.     

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.

     

Largest integral simplices with one interior integral point: Solution of Hensley's conjecture and related results

For each dimension d, d-dimensional integral simplices with exactly one interior integral point have bounded volume. This was first shown by Hensley. Explicit volume bounds were determined by Hensley, Lagarias and Ziegler, Pikhurko, and Averkov. In this paper we determine the exact upper volume bound for such simplices and characterize the volume-maximizing simplices. We also determine the sharp upper bound on the coefficient of asymmetry of an integral polytope with a single interior integral point. This result confirms a conjecture of Hensley from 1983. Moreover, for an integral simplex with precisely one interior integral point, we give bounds on the volumes of its faces, the barycentric coordinates of the interior integral point and its number of integral points. Furthermore, we prove a bound on the lattice diameter of integral polytopes with a fixed number of interior integral points. The presented results have applications in toric geometry and in integer optimization.     

Reconstruction of Convex Bodies from Brightness Functions

Abstract. Algorithms are given for reconstructing an approximation to an unknown convex body from finitely many values of its brightness function, the function giving the volumes of its projections onto hyperplanes. One of these algorithms constructs a convex polytope with less than a prescribed number of facets, while the others do not restrict the number of facets. Convergence of the polytopes to the body is proved under certain essential assumptions including origin symmetry of the body. Also described is an oracle-polynomial-time algorithm for reconstructing an approximation to an origin-symmetric rational convex polytope of fixed and full dimension that is only accessible via its brightness function. Some of the algorithms have been implemented, and sample reconstructions are provided.     

Reconstruction of Convex Bodies from Brightness Functions

   Abstract. Algorithms are given for reconstructing an approximation to an unknown convex body from finitely many values of its brightness function, the function giving the volumes of its projections onto hyperplanes. One of these algorithms constructs a convex polytope with less than a prescribed number of facets, while the others do not restrict the number of facets. Convergence of the polytopes to the body is proved under certain essential assumptions including origin symmetry of the body. Also described is an oracle-polynomial-time algorithm for reconstructing an approximation to an origin-symmetric rational convex polytope of fixed and full dimension that is only accessible via its brightness function. Some of the algorithms have been implemented, and sample reconstructions are provided.     

Coxeter polytopes with a unique pair of non-intersecting facets

We consider compact hyperbolic Coxeter polytopes whose Coxeter diagram contains a unique dotted edge. We prove that such a polytope in d-dimensional hyperbolic space has at most d+3 facets. In view of results by Kaplinskaja [I.M. Kaplinskaya, Discrete groups generated by reflections in the faces of simplicial prisms in Lobachevskian spaces, Math. Notes 15 (1974) 88-91] and the second author [P. Tumarkin, Compact hyperbolic Coxeter n-polytopes with n+3 facets, Electron. J. Combin. 14 (2007), R69, 36 pp.], this implies that compact hyperbolic Coxeter polytopes with a unique pair of non-intersecting facets are completely classified. They do exist only up to dimension 6 and in dimension 8.     

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.     

On the complete set packing and set partitioning polytopes: Properties and rank 1 facets

This paper studies two polytopes: the complete set packing and set partitioning polytopes, which are both associated with a binary $n$-row matrix having all possible columns. Cuts of rank 1 for the latter polytope play a central role in recent exact algorithms for many combinatorial problems, such as vehicle routing. We show the precise relation between the two polytopes studied, characterize the multipliers that induce rank 1 clique facets and give several families of multipliers that yield other facets.     

Covers ℘ for Abstract Regular Polytopes \mathcal {Q} such that \mathcal{Q}=\mathcal{P}/\mathbf{Z}_{p}^{k}

One key problem in the theory of abstract polytopes is the so-called amalgamation problem. In its most general form, this is the problem of characterising the polytopes with given facets  $\mathcal {K}$ and vertex figures ?. The first step in solving it for particular  $\mathcal{K}$ and ? is to find the universal such polytope, which covers all the others. This article explains a construction that may be attempted on an arbitrary polytope ?, which often yields an infinite family of finite polytopes covering ? and sharing its facets and vertex figures. The existence of such an infinite family proves that the universal polytope is infinite; alternatively, the construction can produce an explicit example of an infinite polytope of the desired type. An algorithm for attempting the construction is explained, along with sufficient conditions for it to work. The construction is applied to a few  $\mathcal{K}$ and ? for which it was previously not known whether or not the universal polytope was infinite, or for which only a finite number of finite polytopes was previously known. It is conjectured that the construction is quite broadly applicable.