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.     

Many Neighborly Polytopes and Oriented Matroids

In this paper we present a new technique to construct neighborly polytopes, and use it to prove a lower bound of ${\big (( r+d ) ^{( \frac{r}{2}+\frac{d}{2} )^{2}}\big )}\big /{\big ({r}^{{(\frac{r}{2})}^{2}} {d}^{{(\frac{d}{2})}^{2}}{\mathrm{e}^{3\frac{r}{2}\frac{d}{2}}}\big )}$ for the number of combinatorial types of vertex-labeled neighborly polytopes in even dimension d with $r+d+1$ vertices. This improves current bounds on the number of combinatorial types of polytopes. The previous best lower bounds for the number of neighborly polytopes were found by Shemer in 1982 using a technique called the Sewing Construction. We provide a new simple proof that sewing works, and generalize it to oriented matroids in two ways: to Extended Sewing and to Gale Sewing. Our lower bound is obtained by estimating the number of polytopes that can be constructed via Gale Sewing. Combining both new techniques, we are also able to construct many non-realizable neighborly oriented matroids.     

Quotient polytopes of cyclic polytopes part I: Structure and characterization

We investigate the quotient polytopesC/F, whereC is a cyclic polytope andF is a face ofC. We describe the combinatorial structure of such quotients, and show that under suitable restrictions the pair (C, F) is determined by the combinatorial type ofC/F. We describe alternative constructions of these quotients by “splitting vertices” of lower-dimensional cyclic polytopes. Using Gale diagrams, we show that every simpliciald-polytope withd+3 vertices is isomorphic to a quotient of a cyclic 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.     

Completely unimodal numberings of a simple polytope

A completely unimodal numbering of the m vertices of a simple d-dimensional polytope is a numbering 0, 1, …,m−1 of the vertices such that on every k-dimensional face (2≤k≤d) there is exactly one local minimum (a vertex with no lower-numbered neighbors on that face). Such numberings are abstract objective functions in the sense of Adler and Saigal [1]. It is shown that a completely unimodal numbering of the vertices of a simple polytope induces a shelling of the facets of the dual simplicial polytope. The h-vector of the dual simplicial polytope is interpreted in terms of the numbering (with respect to using a local-improvement algorithm to locate the vertex numbered 0). In the case that the polytope is combinatorially equivalent to a d-dimensional cube, a ‘successor-tuple’ for each vertex is defined which carries the crucial information of the numbering for local-improvement algorithms. Combinatorial properties of these d-tuples are studied. Finally the running time of one particular local-improvement algorithm, the Random Algorithm, is studied for completely unimodal numberings of the d-cube. It is shown that for a certain class of numberings (which includes the example of Klee and Minty [8] showing that the simplex algorithm is not polynomial and all Hamiltonian saddle-free injective pseudo-Boolean functions [6]) this algorithm has expected running time that is at worst quadratic in the dimension d.     

Every Simplicial Polytope with at Most d + 4 Vertices Is a Quotient of a Neighborly Polytope

We show that every simplicial d-polytope with d+4 vertices is a quotient of a neighborly (2d+4)-polytope with 2d+8 vertices, using the technique of affine Gale diagrams. The result is extended to matroid polytopes. Received September 27, 1995.     

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.     

Construction and Analysis of Projected Deformed Products

We introduce a deformed product construction for simple polytopes in terms of lower-triangular block matrix representations. We further show how Gale duality can be employed for the construction and the analysis of deformed products such that specified faces (e.g., all the k-faces) are “strictly preserved” under projection. Thus, starting from an arbitrary neighborly simplicial (d?2)-polytope Q on n?1 vertices, we construct a deformed n-cube, whose projection to the last d coordinates yields a neighborly cubical d -polytope. As an extension of the cubical case, we construct matrix representations of deformed products of (even) polygons (DPPs) which have a projection to d-space that retains the complete $(\lfloor\tfrac{d}{2}\rfloor-1)We introduce a deformed product construction for simple polytopes in terms of lower-triangular block matrix representations. We further show how Gale duality can be employed for the construction and the analysis of deformed products such that specified faces (e.g., all the k-faces) are “strictly preserved” under projection. Thus, starting from an arbitrary neighborly simplicial (d−2)-polytope Q on n−1 vertices, we construct a deformed n-cube, whose projection to the last d coordinates yields a neighborly cubical d -polytope. As an extension of the cubical case, we construct matrix representations of deformed products of (even) polygons (DPPs) which have a projection to d-space that retains the complete (?\tfracd2?-1)(\lfloor\tfrac{d}{2}\rfloor-1) -skeleton.     

Reduced arithmetically Gorenstein schemes and simplicial polytopes with maximal Betti numbers

An SI-sequence is a finite sequence of positive integers which is symmetric, unimodal and satisfies a certain growth condition. These are known to correspond precisely to the possible Hilbert functions of graded Artinian Gorenstein algebras with the weak Lefschetz property, a property shared by a nonempty open set of the family of all graded Artinian Gorenstein algebras having a fixed Hilbert function that is an SI sequence. Starting with an arbitrary SI-sequence, we construct a reduced, arithmetically Gorenstein configuration G of linear varieties of arbitrary dimension whose Artinian reduction has the given SI-sequence as Hilbert function and has the weak Lefschetz property. Furthermore, we show that G has maximal graded Betti numbers among all arithmetically Gorenstein subschemes of projective space whose Artinian reduction has the weak Lefschetz property and the given Hilbert function. As an application we show that over a field of characteristic zero every set of simplicial polytopes with fixed h-vector contains a polytope with maximal graded Betti numbers.     

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.     

Parameter spaces of separating hyperplanes

Every pair of relatively disjoint polytopes is dual to the parameter space of all their separating hyperplanes, which is also a polytope. For a polytope whose interior is disjoint from the relative interior of another polytope, the parameter space of all separating hyperplanes is a polytope of the same dimension. One face of this parameter space parametrizes the separating hyperplanes that also simultaneously support both polytopes. A separating hyperplane corresponds to a vertex of this face if and only if no other hyperplanes support the polytopes at the same intersection points. If all the vertices of the polytopes have all their coordinates in an ordered field, then the same results and their proofs hold with the same ordered field.     

Method for polyhedral approximation of a ball with an optimal order of growth of the facet structure cardinality

The problem of polyhedral approximation of a multidimensional ball is considered. It is well known that the norm of the f-vector (the maximum number of faces of all dimensions) of an approximating polytope grows at least as fast as O(δ^{(1 ? d)/2}), where δ is the Hausdorff deviation and d is the space dimension. An iterative method, namely, the deep holes method is used to construct metric nets. As applied to the problem under study, the method sequentially supplements the vertex set of the polytope with its deep holes in the metric on the ball surface (i.e., with points of the surface that are farthest away from the vertices of the polytope). It is shown that the facet structure cardinality of the constructed polytope has an optimal growth rate. It is also shown that the number of faces of all dimensions in the approximating polytopes generated by the method is asymptotically proportional to the number of their vertices. Closed-form expressions for the constants are obtained, which depend only on the dimension of the space, including the case of high dimensions. For low dimensions (d ranging from 3 to 5), upper bounds for the growth rate of the number of faces of all dimensions are obtained depending on the accuracy of the approximation.     

Efficiency of the estimate refinement method for polyhedral approximation of multidimensional balls

The estimate refinement method for the polyhedral approximation of convex compact bodies is analyzed. When applied to convex bodies with a smooth boundary, this method is known to generate polytopes with an optimal order of growth of the number of vertices and facets depending on the approximation error. In previous studies, for the approximation of a multidimensional ball, the convergence rates of the method were estimated in terms of the number of faces of all dimensions and the cardinality of the facial structure (the norm of the f-vector) of the constructed polytope was shown to have an optimal rate of growth. In this paper, the asymptotic convergence rate of the method with respect to faces of all dimensions is compared with the convergence rate of best approximation polytopes. Explicit expressions are obtained for the asymptotic efficiency, including the case of low dimensions. Theoretical estimates are compared with numerical results.     

A family of neighborly polytopes

Ad-polytopeP is said to be neighborly provided each [d/2] vertices determine a face ofP. We construct a family ofd-polytopes that are dual to neighborly polytopes by means of facet splitting. We use this family to find a lower bound on the number of combinatorial types of neighborly polytopes. We also show that all members of this family satisfy the famous Hirsch conjecture. Research supported by NSF Grant # MCS-07466.     

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.     

Unions of Fat Convex Polytopes Have Short Skeletons

The skeleton of a polyhedral set is the union of its edges and vertices. Let \(\mathcal {P}\) be a set of fat, convex polytopes in three dimensions with n vertices in total, and let f _max be the maximum complexity of any face of a polytope in \(\mathcal {P}\). We prove that the total length of the skeleton of the union of the polytopes in \(\mathcal {P}\) is at most O(α(n)?log^? n?logf _max) times the sum of the skeleton lengths of the individual polytopes.     

Gale diagrams of convex polytopes and positive spanning sets of vectors

The Gale diagram construction assigns a finite set of vectors to a given convex polytope. The resulting correspondence between sets of vectors and convex polytopes is explored here from a new point of view, utilizing the concept of a positive k-spanning set of vectors and a new matrix construction for Gale diagrams.     

Cutting Polytopes and Flag f-Vectors

We show how the flag f -vector of a polytope changes when cutting off any face, generalizing work of Lee for simple polytopes. The result is in terms of explicit linear operators on cd-polynomials. Also, we obtain the change in the flag f -vector when contracting any face of the polytope. Received July 13, 1998, and in revised form April 14, 1999.     

On Polytopes that are Simple at the Edges

We study some combinatorial properties of polytopes that are simple at the edges. We give an elementary geometric proof of an analog of the hard Lefschetz theorem for the polytopes for which the distance between any two nonsimple vertices is sufficiently large. This implies that the h-vector of such polytopes satisfies the relations , where d is the dimension of the polytope, which proves a special case of Stanley's conjecture.     

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.