Random half-integral polytopes

We show that polytopes obtained as the convex hull of a random set of half-integral points of the 0/1 cube have rank as high as Ω(logn/loglogn) with positive probability—even if the size of the set relative to the total number of half-integral points of the cube tends to 0. The high rank is due to certain obstructions. We determine the exact threshold number, when those cease to exist.     

Random polytopes in thed-dimensional cube

LetC ^d be the set of vertices of ad-dimensional cube,C ^d ={(x ₁, ...,x _d ):x _i =±1}. Let us choose a randomn-element subsetA(n) ofC ^d . Here we prove that Prob (the origin belongs to the convA(2d+x2d))=(x)+o(1) ifx is fixed andd . That is, for an arbitrary>0 the convex hull of more than (2+)d vertices almost always contains 0 while the convex hull of less than (2-)d points almost always avoids it.     

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.     

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.     

Note dual polytopes of rational convex polytopes

LetP ^d be a rational convex polytope with dimP=d such that the origin of ^d is contained in the interiorP – P ofP. In this paper, from a viewpoint of enumeration of certain rational points inP (which originated in Ehrhart's work), a necessary and sufficient condition for the dual polytopeP ^dual ofP to be integral is presented.This research was performed while the author was staying at Massachusetts Institute of Technology during the 1988–89 academic year.     

Algebraic shifting of cyclic polytopes and stacked polytopes

Gil Kalai introduced the shifting-theoretic upper bound relation as a method to generalize the g-theorem for simplicial spheres by using algebraic shifting. We will study the connection between the shifting-theoretic upper bound relation and combinatorial shifting. Also, we will compute the exterior algebraic shifted complex of the boundary complex of the cyclic d-polytope as well as of a stacked d-polytope. It will turn out that, in both cases, the exterior algebraic shifted complex coincides with the symmetric algebraic shifted complex.     

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.     

Neighborly polytopes

A 2m-polytopeQ isneighborly if eachm vertices ofQ determine a face. It is shown that the combinatorial structure of a neighborly 2m-polytope determines the combinatorial structure of every subpolytope. We develop a construction of “sewing a vertex onto a polytope”, which, when applied to a neighborly 2m-polytope, yields a neighborly 2m-polytope with one more, vertex. Using this construction, we show that the numberg(2m+β,2m) of combinatorial types of neighborly 2m-polytopes with 2m+β vertices grows superexponentially as β→∞ (m≧2 fixed) and asm→∞ (β≧4 fixed).     

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.     

Hypergraph polytopes

We investigate a family of polytopes introduced by E.M. Feichtner, A. Postnikov and B. Sturmfels, which were named nestohedra. The vertices of these polytopes may intuitively be understood as constructions of hypergraphs. Limit cases in this family of polytopes are, on the one end, simplices, and, on the other end, permutohedra. In between, as notable members one finds associahedra and cyclohedra. The polytopes in this family are investigated here both as abstract polytopes and as realized in Euclidean spaces of all finite dimensions. The later realizations are inspired by J.D. Stasheff ?s and S. Shnider?s realizations of associahedra. In these realizations, passing from simplices to permutohedra, via associahedra, cyclohedra and other interesting polytopes, involves truncating vertices, edges and other faces. The results presented here reformulate, systematize and extend previously obtained results, and in particular those concerning polytopes based on constructions of graphs, which were introduced by M. Carr and S.L. Devadoss.     

Inside-out polytopes

We present a common generalization of counting lattice points in rational polytopes and the enumeration of proper graph colorings, nowhere-zero flows on graphs, magic squares and graphs, antimagic squares and graphs, compositions of an integer whose parts are partially distinct, and generalized latin squares. Our method is to generalize Ehrhart's theory of lattice-point counting to a convex polytope dissected by a hyperplane arrangement. We particularly develop the applications to graph and signed-graph coloring, compositions of an integer, and antimagic labellings.     

Indecomposable polytopes

The notions of local similarity and decomposability are extended to the class of geometric graphs. These, in turn, are used to produce new sufficient conditions for indecomposability of polytopes. A simple example is given of two combinatorially equivalent 3-polytopes, one decomposable, and the other not. The content of this paper is an extension of a part of a Ph.D. thesis [3], written by the author under the supervision of Professor M. A. Perles at the Hebrew University of Jerusalem, and submitted in April 1979.     

Weights on polytopes

Theg-theorem describes the possible face-vectors of a simple polytopeP. Much of the author's proof of the necessity of its conditions, while working within the polytope algebra π, in fact only used the spaces of weights onP. Even though this proof was conceptually easier than the original, which employed techniques from algebraic geometry, nevertheless the properties of π which are needed still require some effort to establish, despite a recent simpler approach to π itself. In the earlier paper, doubt was expressed about whether two basic results could be proved directly for weights; later, it appeared that there might also be a possible problem concerning an alternative definition of the product of certain weights. In this paper these questions are settled, in the context of developing an independent theory of an algebra Ω of weights on polytopes. Since the construction of Ω is more approachable than that of π, a yet easier proof of theg-theorem is now available.     

Eulerian abstract polytopes

The classical theory of regular convex polytopes has inspired many combinatorial analogues. In this article, we examine two of them, the eulerian posets and the abstract regular polytopes, and see what the overlap between the concepts is. It is shown that a section regular polytope is eulerian if and only if it is spherical, or it has even rank and is locally spherical. Equivelar polytopes of rank less than 4 are eulerian, and some progress is made towards a characterisation of equivelar eulerian posets in higher rank. In particular, necessary conditions are given for an equivelar quotient of a cube or a torus to be eulerian.     

Hamiltonian simple polytopes

We show that for everyn> n _o (d) (n even ifd is odd) there exists a simpled-polytope withn vertices, whose graph admits a Hamiltonian circuit. The result sharpens and earlier lower bound due to Victor Klee.