Semisymmetric graphs from polytopes

Every finite, self-dual, regular (or chiral) 4-polytope of type {3,q,3} has a trivalent 3-transitive (or 2-transitive) medial layer graph. Here, by dropping self-duality, we obtain a construction for semisymmetric trivalent graphs (which are edge- but not vertex-transitive). In particular, the Gray graph arises as the medial layer graph of a certain universal locally toroidal regular 4-polytope.     

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.     

Locally toroidal polytopes and modular linear groups

When the standard representation of a crystallographic Coxeter group G (with string diagram) is reduced modulo the integer d≥2, one obtains a finite group G^d which is often the automorphism group of an abstract regular polytope. Building on earlier work in the case that d is an odd prime, here we develop methods to handle composite moduli and completely describe the corresponding modular polytopes when G is of spherical or Euclidean type. Using a modular variant of the quotient criterion, we then describe the locally toroidal polytopes provided by our construction, most of which are new.     

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.     

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.     

On perimeters of sections of convex polytopes

In his book “Geometric Tomography” Richard Gardner asks the following question. Let P and Q be origin-symmetric convex bodies in R³ whose sections by any plane through the origin have equal perimeters. Is it true that P=Q? We show that the answer is “Yes” in the class of origin-symmetric convex polytopes. The problem is treated in the general case of Rn.     

All regular polytopes are Ramsey

In this paper it is shown that all regular polytopes are Ramsey. In the course of this proof all convex quasi-regular polyhedra are proved to be Ramsey.     

A new Petrie-like construction for abstract polytopes

This article introduces a new construction for polytopes, that may be seen as a generalisation of the Petrie dual to higher ranks. Some theoretical results are derived regarding when the construction can be expected to work, and the construction is applied to some special cases. In particular, the generalised Petrie duals of the hypercubes are enumerated.     

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.     

Lattices generated by skeletons of reflexive polytopes

Lattices generated by lattice points in skeletons of reflexive polytopes are essential in determining the fundamental group and integral cohomology of Calabi-Yau hypersurfaces. Here we prove that the lattice generated by all lattice points in a reflexive polytope is already generated by lattice points in codimension two faces. This answers a question of John Morgan.     

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.     

Vertex embeddings of regular polytopes

The question of when one regular polytope (finite, convex) embedds in the vertices of another, of the same dimension, leads to a fascinating interplay of geometry, combinatorics, and matrix theory, with further relations to number theory and algebraic topology. This mainly expository paper is an account of this subject, its history, and the principal results together with an outline of their proofs. The relationships with other branches of mathematics are also explained.     

Extensions of regular polytopes with preassigned Schläfli symbol

We say that a (d+1)-polytope P is an extension of a polytope K if the facets or the vertex figures of P are isomorphic to K. The Schläfli symbol of any regular extension of a regular polytope is determined except for its first or last entry. For any regular polytope K we construct regular extensions with any even number as first entry of the Schläfli symbol. These extensions are lattices if K is a lattice. Moreover, using the so-called CPR graphs we provide a more general way of constructing extensions of polytopes.     

Graphs of transportation polytopes

This paper discusses properties of the graphs of 2-way and 3-way transportation polytopes, in particular, their possible numbers of vertices and their diameters. Our main results include a quadratic bound on the diameter of axial 3-way transportation polytopes and a catalogue of non-degenerate transportation polytopes of small sizes. The catalogue disproves five conjectures about these polyhedra stated in the monograph by Yemelichev et al. (1984). It also allowed us to discover some new results. For example, we prove that the number of vertices of an m×n transportation polytope is a multiple of the greatest common divisor of m and n.     

Equivalence of permutation polytopes corresponding to strictly supermodular functions

This paper demonstrates a strong equivalence of all permutation polytopes corresponding to strictly supermodular functions.     

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.     

Correlation polytopes: Their geometry and complexity

A family of polytopes, correlation polytopes, which arise naturally in the theory of probability and propositional logic, is defined. These polytopes are tightly connected to combinatorial problems in the foundations of quantum mechanics, and to the Ising spin model. Correlation polytopes exhibit a great deal of symmetry. Exponential size symmetry groups, which leave the polytope invariant and act transitively on its vertices, are defined. Using the symmetries, a large family of facets is determined. A conjecture concerning the full facet structure of correlation polytopes is formulated (the conjecture, however, implies that NP=co-NP).Various complexity results are proved. It is shown that deciding membership in a correlation polytope is an NP-complete problem, and deciding facets is probably not even in NP. The relations between the polytope symmetries and its complexity are indicated.     

Classification of lattice-regular lattice convex polytopes

We completely describe lattice convex polytopes in ℝ ⁿ (for any dimension n) that are regular with respect to the group of affine transformations preserving the lattice. Supported in part by the RFBR (Grant Nos. SS-1972.2003.1 and 05-01-01012a) and the NWO-RFBR (Grant No. 047.011.2004.026/RFBR No. 05-02-89000-NWO_a).