Inequalities for <Emphasis Type="Bold">cd</Emphasis>-Indices of Joins and Products of Polytopes

The cd-index is a polynomial which encodes the flag f-vector of a convex polytope. For polytopes U and V, we determine explicit recurrences for computing the cd-index of the free join and the cd-index of the Cartesian product U x V. As an application of these recurrences, we prove the inequality involving the cd-indices of three polytopes.     

Equipartite polytopes

A polytope P with 2n vertices is called equipartite if for any partition of its vertex set into two equal-size sets V ₁ and V ₂, there is an isometry of the polytope P that maps V ₁ onto V ₂. We prove that an equipartite polytope in ℝ ^d can have at most 2d+2 vertices. We show that this bound is sharp and identify all known equipartite polytopes in ℝ ^d . We conjecture that the list is complete.     

How many cyclic subpolytopes can a non-cyclic polytope have?

Acyclic d-polytope is ad-polytope that is combinatorially equivalent to a polytope whose vertices lie on the moment curve {(t, t ², …,t ^d):t∈R}. Every subpolytope of an even-dimensional cyclic polytope is again cyclic. We show that a polytope [or neighborly polytope] withv vertices that is not cyclic has at mostd+1 [respectivelyd]d-dimensional cyclic subpolytopes withv−1 vertices, providedd is even andv≧d+5.     

Embedding a polytope in a lattice

We present a special similarity ofR ⁴ⁿ which maps lattice points into lattice points. Applying this similarity, we prove that if a (4n−1)-polytope is similar to a lattice polytope (a polytope whose vertices are all lattice points) inR ⁴ⁿ , then it is similar to a lattice polytope inR ⁴ⁿ⁻¹, generalizing a result of Schoenberg [4]. We also prove that ann-polytope is similar to a lattice polytope in someR ^N if and only if it is similar to a lattice polytope inR ²ⁿ⁺¹, and if and only if sin²(<ABC) is rational for any three verticesA, B, C of the 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.     

A bound for the number of vertices of a polytope with applications

We prove that the number of vertices of a polytope of a particular kind is exponentially large in the dimension of the polytope. As a corollary, we prove that an n-dimensional centrally symmetric polytope with O(n) facets has {ie1-1} vertices and that the number of r-factors in a k-regular graph is exponentially large in the number of vertices of the graph provided k≥2r+1 and every cut in the graph with at least two vertices on each side has more than k/r edges.     

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.     

Long monotone paths on simple 4-polytopes

TheMonotone Upper Bound Problem (Klee, 1965) asks if the maximal numberM(d,n) of vertices in a monotone path along edges of ad-dimensional polytope withn facets can be as large as conceivably possible: IsM(d,n)=M _ubt (d,n), the maximal number of vertices that ad-polytope withn facets can have according to the Upper Bound Theorem?We show that in dimensiond=4, the answer is “yes”, despite the fact that it is “no” if we restrict ourselves to the dual-to-cyclic polytopes. For eachn≥5, we exhibit a realization of a polar-to-neighborly 4-dimensional polytope withn facets and a Hamilton path through its vertices that is monotone with respect to a linear objective function.This constrasts an earlier result, by which no polar-to-neighborly 6-dimensional polytope with 9 facets admits a monotone Hamilton path.     

Hamiltonian Submanifolds of Regular Polytopes

We investigate polyhedral 2k-manifolds as subcomplexes of the boundary complex of a regular polytope. We call such a subcomplex k -Hamiltonian if it contains the full k-skeleton of the polytope. Since the case of the cube is well known and since the case of a simplex was also previously studied (these are so-called super-neighborly triangulations), we focus on the case of the cross polytope and the sporadic regular 4-polytopes. By our results the existence of 1-Hamiltonian surfaces is now decided for all regular polytopes. Furthermore we investigate 2-Hamiltonian 4-manifolds in the d-dimensional cross polytope. These are the “regular cases” satisfying equality in Sparla’s inequality. In particular, we present a new example with 16 vertices which is highly symmetric with an automorphism group of order 128. Topologically it is homeomorphic to a connected sum of seven copies of S ²×S ². By this example all regular cases of n vertices with n<20 or, equivalently, all cases of regular d-polytopes with d≤9 are now decided.     

A Centrally Symmetric Version of the Cyclic Polytope

We define a centrally symmetric analogue of the cyclic polytope and study its facial structure. We conjecture that our polytopes provide asymptotically the largest number of faces in all dimensions among all centrally symmetric polytopes with n vertices of a given even dimension d=2k when d is fixed and n grows. For a fixed even dimension d=2k and an integer 1≤j<k we prove that the maximum possible number of j-dimensional faces of a centrally symmetric d-dimensional polytope with n vertices is at least for some c _j (d)>0 and at most as n grows. We show that c ₁(d)≥1−(d−1)⁻¹ and conjecture that the bound is best possible. Research of A. Barvinok partially supported by NSF grant DMS 0400617. Research of I. Novik partially supported by Alfred P. Sloan Research Fellowship and NSF grant DMS-0500748.     

Gaps in the numbers of vertices of cubical polytopes,I

A cubical polytope is a convex polytope of which very facet is a combinatorial cube. We ask for the numbers which occur as vertex numbers ofd-dimensional cubical polytopes, and we show, as a first step, that every cubicald-polytope for evend≥4 has an even number of vertices.     

New Combinatorial Descriptions of the Triangulations of Cyclic Polytopes and the Second Higher Stasheff–Tamari Posets

This paper is concerned with the d-dimensional cyclic polytope with n vertices, C(n,d), and the set of its triangulations, S(n,d). We show that there is a bijection between S(n,d) and certain partitions of the set of increasing d-tuples on the integers 1 to n–1. We give a combinatorial characterization of the second higher Stasheff–Tamari poset, which is a partial ordering of S(n,d), and we determine its 2-dimension. There is a well-known representation of triangulations of an n-gon by right bracket vectors. We generalize this to cyclic polytopes of higher dimensions.     

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.     

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.     

Polytopes which are orthogonal projections of regular simplexes

We consider the polytopes which are certain orthogonal projections of k-dimensional regular simplexes in k-dimensional Euclidean space R ^k . We call such polytopes -polytopes. Every sufficiently symmetric polytope, such as a regular polytope, a quasi-regular polyhedron, etc., belongs to this class. We denote by P _m,n all n-dimensional -polytopes with m vertices. We show that there is a one-to-one correspondence between the elements of P _m,n and those of P _m,m–n–1 and that this correspondence preserves the symmetry of -polytopes. Using this duality, we determine some of the P _m,n 's. We also show that a -polytope is an orthogonal projection of a cross polytope if and only if it has central symmetry.     

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.     

The r-cubical Lattice and a Generalization of the cd-index

In this paper we generalize thecd-index of the cubical lattice to anr-cd-index, which we denote byΨ(r). The coefficients ofΨ(r) enumerate augmented Andrér-signed permutations, a generalization of Purtill's work relating thecd-index of the cubical lattice and signed André permutations. As an application we use ther-cd-index to determine that the extremal configuration which maximizes the Möbius function of arbitrary rank selections, where all ther_i's are greater than one, is the odd alternating ranks, {1, 3, 5, ...}.     

On the Discrepancy for Boxes and Polytopes

 We consider so-called Tusnády’s problem in dimension d: Given an n-point set P in R ^d , color the points of P red or blue in such a way that for any d-dimensional interval B, the number of red points in differs from the number of blue points in by at most Δ, where should be as small as possible. We slightly improve previous results of Beck, Bohus, and Srinivasan by showing that , with a simple proof. The same asymptotic bound is shown for an analogous problem where B is allowed to be any translated and scaled copy of a fixed convex polytope A in R ^d . Here the constant of proportionality depends on A and we give an explicit estimate. The same asymptotic bounds also follow for the Lebesgue-measure discrepancy, which improves and simplifies results of Beck and of Károlyi.     

Fire containment in grids of dimension three and higher

We consider a deterministic discrete-time model of fire spread introduced by Hartnell [Firefighter! an application of domination, Presentation, in: 20th Conference on Numerical Mathematics and Computing, University of Manitoba in Winnipeg, Canada, September 1995] and the problem of minimizing the number of burnt vertices when a fixed number of vertices can be defended by firefighters per time step. While only two firefighters per time step are needed in the two-dimensional lattice to contain any outbreak, we prove a conjecture of Wang and Moeller [Fire control on graphs, J. Combin. Math. Combin. Comput. 41 (2002) 19-34] that 2d-1 firefighters per time step are needed to contain a fire outbreak starting at a single vertex in the d-dimensional square lattice for d?3; we also prove that in the d-dimensional lattice, d?3, for each positive integer f there is some outbreak of fire such that f firefighters per time step are insufficient to contain the outbreak. We prove another conjecture of Wang and Moeller that the proportion of elements in the three-dimensional grid P_n×P_n×P_n which can be saved with one firefighter per time step when an outbreak starts at one vertex goes to 0 as n gets large. Finally, we use integer programming to prove results about the minimum number of time steps needed and minimum number of burnt vertices when containing a fire outbreak in the two-dimensional square lattice with two firefighters per time step.     

Quasisymmetric functions and Kazhdan-Lusztig polynomials

We associate a quasisymmetric function to any Bruhat interval in a general Coxeter group. This association can be seen to be a morphism of Hopf algebras to the subalgebra of all peak functions, leading to an extension of the cd-index of convex polytopes. We show how the Kazhdan-Lusztig polynomial of the Bruhat interval can be expressed in terms of this complete cd-index and otherwise explicit combinatorially defined polynomials. In particular, we obtain the simplest closed formula for the Kazhdan-Lusztig polynomials that holds in complete generality.