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.     

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.     

On edge-antipodal <Emphasis Type="Italic">d</Emphasis>-polytopes

A convex d-polytope in ℝ ^d is called edge-antipodal if any two vertices that determine an edge of the polytope lie on distinct parallel supporting hyperplanes of the polytope. We introduce a program for investigating such polytopes, and examine those that are simple.      

Zonotopes whose cellular strings are all coherent

A cellular string of a polytope is a sequence of faces stacked on top of each other in a given direction. The poset of cellular strings, ordered by refinement, is known to be homotopy equivalent to a sphere. The subposet of coherent cellular strings is the face lattice of the fiber polytope, hence is homeomorphic to a sphere. In some special cases, every cellular string is coherent. Such polytopes are said to be all-coherent. We give a complete classification of zonotopes with the all-coherence property in terms of their oriented matroid structure. Although the face lattice of the fiber polytope in this case is not an oriented matroid invariant, we prove that the all-coherence property is invariant.     

Lines Pinning Lines

A line ℓ is a transversal to a family F of convex polytopes in ℝ³ if it intersects every member of F. If, in addition, ℓ is an isolated point of the space of line transversals to F, we say that F is a pinning of ℓ. We show that any minimal pinning of a line by polytopes in ℝ³ such that no face of a polytope is coplanar with the line has size at most eight. If in addition the polytopes are pairwise disjoint, then it has size at most six.     

On hyperbolic Coxeter polytopes with mutually intersecting facets

We prove that, apart from some well-known low-dimensional examples, any compact hyperbolic Coxeter polytope has a pair of disjoint facets. This is one of very few known general results concerning combinatorics of compact hyperbolic Coxeter polytopes. We also obtain a similar result for simple non-compact polytopes.     

Gelfand-Tsetlin polytopes and Feigin-Fourier-Littelmann-Vinberg polytopes as marked poset polytopes

Stanley (1986) showed how a finite partially ordered set gives rise to two polytopes, called the order polytope and chain polytope, which have the same Ehrhart polynomial despite being quite different combinatorially. We generalize his result to a wider family of polytopes constructed from a poset P with integers assigned to some of its elements.Through this construction, we explain combinatorially the relationship between the Gelfand-Tsetlin polytopes (1950) and the Feigin-Fourier-Littelmann-Vinberg polytopes (2010, 2005), which arise in the representation theory of the special linear Lie algebra. We then use the generalized Gelfand-Tsetlin polytopes of Berenstein and Zelevinsky (1989) to propose conjectural analogues of the Feigin-Fourier-Littelmann-Vinberg polytopes corresponding to the symplectic and odd orthogonal Lie algebras.     

Möbius Polynomials of Face Posets of Convex Polytopes

The Möbius polynomial is an invariant of ranked posets, closely related to the Möbius function. In this paper, we study the Möbius polynomial of face posets of convex polytopes. We present formulas for computing the Möbius polynomial of the face poset of a pyramid or a prism over an existing polytope, or of the gluing of two or more polytopes in terms of the Möbius polynomials of the original polytopes. We also present general formulas for calculating Möbius polynomials of face posets of simplicial polytopes and of Eulerian posets in terms of their f-vectors and some additional constraints.     

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.     

f-Vectors of Minkowski Additions of Convex Polytopes

The objective of this paper is to present two types of results on Minkowski sums of convex polytopes. The first is about a special class of polytopes we call perfectly centered and the combinatorial properties of the Minkowski sum with their own dual. In particular, we have a characterization of the face lattice of the sum in terms of the face lattice of a given perfectly centered polytope. Exact face counting formulas are then obtained for perfectly centered simplices and hypercubes. The second type of results concerns tight upper bounds for the f-vectors of Minkowski sums of several polytopes.     

Accurately learning from few examples with a polyhedral classifier

In the context of learning theory many efforts have been devoted to developing classification algorithms able to scale up with massive data problems. In this paper the complementary issue is addressed, aimed at deriving powerful classification rules by accurately learning from few data. This task is accomplished by solving a new mixed integer programming model that extends the notion of discrete support vector machines, in order to derive an optimal set of separating hyperplanes for binary classification problems. According to the cardinality of the set of hyperplanes, the classification region may take the form of a convex polyhedron or a polytope in the original space where the examples are defined. Computational tests on benchmark datasets highlight the effectiveness of the proposed model, that yields the greatest accuracy when compared to other classification approaches. This research was partially supported by PRIN grant 2004132117.     

The existence of non-tiles and non-facets in three dimensions

Non-tiles are convex polytopes, of which isomorphic copies will not tile the space locally finite and face-to-face (that is, neighbouring tiles meet in a face of each). Non-facets are convex polytopes, of which isomorphic copies will not fit together as the facets of a higher dimensional convex polytope. It is proved that there are infinitely many 3-dimensional convex polytopes which are non-tiles as well as non-facets, thereby answering a question of Danzer.     

The graph of an abstract polytope

Recently a generalization of simple convex polytopes to combinatorial entities known as abstract polytopes has been proposed. The graph of an abstract polytope of dimensiond is a regular connected graph of degreed. Given a connected regular graph of degreed, it is interesting to find out whether it is the graph of some abstract polytopeP. We obtain necessary and sufficient conditions for this, in terms of the existence of a class of simple cycles in satisfying certain properties. The main result in this paper is that if a pair of simple convex polytopes or abstract polytopes have the same two-dimensional skeleton, then they are isomorphic. Every two-dimensional face of a simple convex polytope or an abstract polytope is a simple cycle in its graph. Given the graph of a simple convex polytope or an abstract polytope and the simple cycles in this graph corresponding to all its two-dimensional faces, then we show how to construct all its remaining faces. Given a regular connected graph and a class of simple cylesD in it, we provide necessary and sufficient conditions under whichD is the class of two-dimensional faces of some abstract polytope which has as its graph.This research has been partially supported by the ISDOS Research Project at the Department of Industrial and Operations Engineering, and by the National Science Foundation under Grant No. GK-27872 with the University of Michigan.     

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.     

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.     

Self-Duality of Polytopes and its Relations to Vertex Enumeration and Graph Isomorphism

We study the complexity of determining whether a polytope given by its vertices or facets is combinatorially isomorphic to its polar dual. We prove that this problem is Graph Isomorphism hard, and that it is Graph Isomorphism complete if and only if Vertex Enumeration is Graph Isomorphism easy. To the best of our knowledge, this is the first problem that is not equivalent to Vertex Enumeration and whose complexity status has a non-trivial impact on the complexity of Vertex Enumeration irrespective of whether checking Self-duality turns out to be strictly harder than Graph Isomorphism or equivalent to Graph Isomorphism. The constructions employed in the proof yield a class of self-dual polytopes that are interesting on their own. In particular, this class of self-dual polytopes has the property that the facet-vertex incident matrix of the polytope is transposable if and only if the matrix is symmetrizable as well. As a consequence of this construction, we also prove that checking self-duality of a polytope, given by its facet-vertex incidence matrix, is Graph Isomorphism complete, thereby answering a question of Kaibel and Schwartz.     

Regular Polytopes of Full Rank

The dimension of a faithful realization of a finite abstract regular polytope in some euclidean space is no smaller than its rank. Similarly, that of a discrete faithful realization of a regular apeirotope is at least one fewer than the rank. Realizations which attain the minimum are said to be of full rank. The regular polytopes and apeirotopes of full rank in two and three dimensions were classified in an earlier paper. In this paper these polytopes and apeirotopes are classified in all dimensions. Moreover, it is also shown that there are no chiral polytopes of full rank.     

Essential hyperbolic Coxeter polytopes

We introduce a notion of an essential hyperbolic Coxeter polytope as a polytope which fits some minimality conditions. The problem of classification of hyperbolic reflection groups can be easily reduced to classification of essential Coxeter polytopes. We determine a potentially large combinatorial class of polytopes containing, in particular, all the compact hyperbolic Coxeter polytopes of dimension at least 6 which are known to be essential, and prove that this class contains finitely many polytopes only. We also construct an effective algorithm of classifying polytopes from this class, realize it in the four-dimensional case, and formulate a conjecture on finiteness of the number of essential polytopes.