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.     

Central limit theorems for random polytopes

Let K be a smooth convex set. The convex hull of independent random points in K is a random polytope. Central limit theorems for the volume and the number of i dimensional faces of random polytopes are proved as the number of random points tends to infinity. One essential step is to determine the precise asymptotic order of the occurring variances. Research was supported in part by the European Network PHD, MCRN-511953.     

On the f-vectors of the pyramidal triangulations of point configurations

A triangulation of a point configuration is called pyramidal if all its simplices have a vertex in common. A series of inequalities are derived for the components of the f-vectors of pyramidal triangulations, and, for every d ≥ 3, a d-dimensional convex polytope and its triangulation are constructed whose f-vector cannot be realized as the f-vector of a pyramidal triangulation.     

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.     

Equidecomposable and weakly neighborly polytopes

A polytope is equidecomposable if all its triangulations have the same face numbers. For an equidecomposable polytope all minimal affine dependencies have an equal number of positive and negative coefficients. A subclass consists of the weakly neighborly polytopes, those for which every set of vertices is contained in a face of at most twice the dimension as the set. Theh-vector of every triangulation of a weakly neighborly polytope equals theh-vector of the polytope itself. Combinatorial properties of this class of polytopes are studied. Gale diagrams of weakly neighborly polytopes with few vertices are characterized in the spirit of the known Gale diagram characterization of Lawrence polytopes, a special class of weakly neighborly 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.     

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.     

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.     

Upper bounds for edge-antipodal and subequilateral polytopes

A polytope in a finite-dimensional normed space is subequilateral if the length in the norm of each of its edges equals its diameter. Subequilateral polytopes occur in the study of two unrelated subjects: surface energy minimizing cones and edge-antipodal polytopes. We show that the number of vertices of a subequilateral polytope in any d-dimensional normed space is bounded above by (d / 2 + 1) ^d for any d ≥ 2. The same upper bound then follows for the number of vertices of the edge-antipodal polytopes introduced by I. Talata [19]. This is a constructive improvement to the result of A. Pór (to appear) that for each dimension d there exists an upper bound f(d) for the number of vertices of an edge-antipodal d-polytopes. We also show that in d-dimensional Euclidean space the only subequilateral polytopes are equilateral simplices. This material is based upon work supported by the South African National Research Foundation under Grant number 2053752.     

Projection problems for symmetric polytopes

Let K⊂Rn be a convex body (a compact, convex subset with non-empty interior), ΠK its projection body. Finding the least upper bound, as K ranges over the class of origin-symmetric convex bodies, of the affine-invariant ratio V(ΠK)/V(K)ⁿ⁻¹, being called Schneider's projection problem, is a well-known open problem in the convex geometry. To study this problem, Lutwak, Yang and Zhang recently introduced a new affine invariant functional for convex polytopes in Rn. For origin-symmetric convex polytopes, they posed a conjecture for the new functional U(P). In this paper, we give an affirmative answer to the conjecture in Rn, thereby, obtain a modified version of Schneider's projection problem.     

Computational results on an algorithm for finding all vertices of a polytope

This paper provides answers to several questions raised by V. Klee regarding the efficacy of Mattheiss' algorithm for finding all vertices of convex polytopes. Several results relating to the expected properties of polytopes are given which indicate thatn-polytopes defined by large numbers of constraints are difficult to obtain by random processes, the expected value of the number of vertices of polytope is considerably less than Klee's least upper bound the expected performance of Mattheiss' algorithm is far better than Klee's upper bound would suggest.     

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.     

Reguläre Inzidenzkomplexe II

The concept of regular incidence complexes generalizes the notion of regular polyhedra in a combinatorial and grouptheoretical sense. A regular (incidence) complex K is a special type of partially ordered structure with regularity defined by the flag-transitivity of its group A(K) of automorphisms. The structure of a regular complex K can be characterized by certain sets of generators and ‘relations’ of its group. The barycentric subdivision of K leads to a simplicial complex, from which K can be rebuilt by fitting together faces. Moreover, we characterize the groups that act flag-transitively on regular complexes. Thus we have a correspondence between regular complexes on the one hand and certain groups on the other hand. Especially, this principle is used to give a geometric representation for an important class of regular complexes, the so-called regular incidence polytopes. There are certain universal incidence polytopes associated to Coxeter groups with linear diagram, from which each regular incidence polytope can be deduced by identifying faces. These incidence polytopes admit a geometric representation in the real space by convex cones.     

Random polytopes: Their definition,generation and aggregate properties

The definition of random polytope adopted in this paper restricts consideration to those probability measures satisfying two properties. First, the measure must induce an absolutely continuous distribution over the positions of the bounding hyperplanes of the random polytope; and second, it must result in every point in the space being equally as likely as any other point of lying within the random polytope. An efficient Monte Carlo method for their computer generation is presented together with analytical formulas characterizing their aggregate properties. In particular, it is shown that the expected number of extreme points for such random polytopes increases monotonically in the number of constraints to the limiting case of a polytope topologically equivalent to a hypercube. The implied upper bound of 2 ⁿ wheren is the dimensionality of the space is significantly less than McMullen's attainable bound on the maximal number of vertices even for a moderate number of constraints.     

Lifting inequalities for polytopes

We present a method of lifting linear inequalities for the flag f-vector of polytopes to higher dimensions. Known inequalities that can be lifted using this technique are the non-negativity of the toric g-vector and that the simplex minimizes the cd-index. We obtain new inequalities for six-dimensional polytopes. In the last section we present the currently best known inequalities for dimensions 5 through 8.     

A sweep-plane algorithm for generating random tuples in simple polytopes

A sweep-plane algorithm of Lawrence for convex polytope computation is adapted to generate random tuples on simple polytopes. In our method an affine hyperplane is swept through the given polytope until a random fraction (sampled from a proper univariate distribution) of the volume of the polytope is covered. Then the intersection of the plane with the polytope is a simple polytope with smaller dimension.

In the second part we apply this method to construct a black-box algorithm for log-concave and -concave multivariate distributions by means of transformed density rejection.

     

Nerve complexes and moment-angle spaces of convex polytopes

We introduce spherical nerve complexes that are a far-reaching generalization of simplicial spheres, and consider the differential ring of simplicial complexes. We show that spherical nerve complexes form a subring of this ring, and define a homomorphism from the ring of polytopes to this subring that maps each polytope P to the nerve K _P of the cover of the boundary ∂P by facets. We develop a theory of nerve complexes and apply it to the moment-angle spaces Z _P of convex polytopes P. In the case of a polytope P with m facets, its moment-angle space Z _P is defined by the canonical embedding in the cone ℝ_≥ ^m . It is well-known that the space Z _P is homeomorphic to the polyhedral product (D ², S ¹)∂P* if the polytope P is simple. We show that the homotopy equivalence Z_P @ (D² ,S¹ )^K_P \mathcal{Z}_P \simeq (D^2 ,S^1 )^{K_P } holds in the general case. On the basis of bigraded Betti numbers of simplicial complexes, we construct a new class of combinatorial invariants of convex polytopes. These invariants take values in the ring of polynomials in two variables and are multiplicative with respect to the direct product or join of polytopes. We describe the relation between these invariants and the well-known f-polynomials of polytopes. We also present examples of convex polytopes whose flag numbers (in particular, f-polynomials) coincide, while the new invariants are different.     

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.     

Mixing chiral polytopes

An abstract polytope of rank n is said to be chiral if its automorphism group has two orbits on the flags, such that adjacent flags belong to distinct orbits. Examples of chiral polytopes have been difficult to find. A ??mixing?? construction lets us combine polytopes to build new regular and chiral polytopes. By using the chirality group of a polytope, we are able to give simple criteria for when the mix of two polytopes is chiral.     

On toric h-vectors of centrally symmetric polytopes

We prove tight lower bounds for the coefficients of the toric h-vector of an arbitrary centrally symmetric polytope generalizing previous results due to R. Stanley and the author using toric varieties. Our proof here is based on the theory of combinatorial intersection cohomology for normal fans of polytopes developed by G. Barthel, J.-P. Brasselet, K. Fieseler and L. Kaup, and independently by P. Bressler and V. Lunts. This theory is also valid for nonrational polytopes when there is no standard correspondence with toric varieties. In this way we can establish our bounds for centrally symmetric polytopes even without requiring them to be rational. Received: 24 March 2004