Determinants and the volumes of parallelotopes and zonotopes

The Minkowski sum of edges corresponding to the column vectors of a matrix A with real entries is the same as the image of a unit cube under the linear transformation defined by A with respect to the standard bases. The geometric object obtained in this way is a zonotope, Z(A). If the columns of the matrix are linearly independent, the object is a parallelotope, P(A). In the first section, we derive formulas for the volume of P(A) in various ways as , as the square root of the sum of the squares of the maximal minors of A, and as the product of the lengths of the edges of P(A) times the square root of the determinant of the matrix of cosines of angles between pairs of edges. In the second section, we use the volume formulas to derive real-case versions of several well-known determinantal inequalities—those of Hadamard, Fischer, Koteljanskii, Fan, and Szasz—involving principal minors of a positive-definite Hermitian matrix. In the last section, we consider zonotopes, obtain a new proof of the decomposition of a zonotope into its generating parallelotopes, and obtain a volume formula for Z(A).     

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.     

A class of bounds for convex bodies in Hilbert space

We extend to infinite dimensions a class of bounds forL _p metrics of finite-dimensional convex bodies. A generalization to arbitrary increasing convex functions is done simultaneously. The main tool is the use of Gaussian measure to effect a normalization for varying dimension. At a point in the proof we also invoke a strong law of large numbers for random sets to produce a rotational averaging.Supported in part by ONR Grant N0014-90-J-1641 and NSF Grant DMS-9002665.     

The isoperimetric inequality and Q-curvature

A well-known question in differential geometry is to control the constant in isoperimetric inequality by intrinsic curvature conditions. In dimension 2, the constant can be controlled by the integral of the positive part of the Gaussian curvature. In this paper, we showed that on simply connected conformally flat manifolds of higher dimensions, the role of the Gaussian curvature can be replaced by the Branson's Q  -curvature. We achieve this by exploring the relationship between _Ap$A_p$ weights and integrals of the Q-curvature.     

Spherical containment and the Minkowski dimension of partial orders

The recent work on circle orders generalizes to higher dimensional spheres. As spherical containment is equivalent to causal precedence in Minkowski space, we define the Minkowski dimension of a poset to be the dimension of the minimal Minkowski space into which the poset can be embedded; this isd if the poset can be represented by containment with spheresS ^d–2 and of no lower dimension. Comparing this dimension with the standard dimension of partial orders we prove that they are identical in dimension two but not in higher dimensions, while their irreducible configurations are the same in dimensions two and three. Moreover, we show that there are irreducible configurations for arbitrarily large Minkowski dimension, thus providing a lower bound for the Minkowski dimension of partial orders.     

On the nontrivial projection problem

The nontrivial projection problem asks whether every finite-dimensional normed space admits a well-bounded projection of nontrivial rank and corank or, equivalently, whether every centrally symmetric convex body (of arbitrary dimension) is approximately affinely equivalent to a direct product of two bodies of nontrivial dimensions. We show that this is true “up to a logarithmic factor.”     

Capacities, surface area, and radial sums

A dual capacitary Brunn-Minkowski inequality is established for the (n−1)-capacity of radial sums of star bodies in Rn. This inequality is a counterpart to the capacitary Brunn-Minkowski inequality for the p-capacity of Minkowski sums of convex bodies in Rn, 1?p<n, proved by Borell, Colesanti, and Salani. When n?3, the dual capacitary Brunn-Minkowski inequality follows from an inequality of Bandle and Marcus, but here a new proof is given that provides an equality condition. Note that when n=3, the (n−1)-capacity is the classical electrostatic capacity. A proof is also given of both the inequality and a (different) equality condition when n=2. The latter case requires completely different techniques and an understanding of the behavior of surface area (perimeter) under the operation of radial sum. These results can be viewed as showing that in a sense (n−1)-capacity has the same status as volume in that it plays the role of its own dual set function in the Brunn-Minkowski and dual Brunn-Minkowski theories.     

Minimal and reduced pairs of convex bodies

We give a new proof for the existence and uniqueness (up to translation) of plane minimal pairs of convex bodies in a given equivalence class of the Hörmander-R»dström lattice, as well as a complete characterization of plane minimal pairs using surface area measures. Moreover, we introduce the so-called reduced pairs, which are special minimal pairs. For the plane case, we characterize reduced pairs as those pairs of convex bodies whose surface area measures are mutually singular. For higher dimensions, we give two sufficient conditions for the minimality of a pair of convex polytopes, as well as a necessary and sufficient criterion for a pair of convex polytopes to be reduced. We conclude by showing that a typical pair of convex bodies, in the sense of Baire category, is reduced, and hence the unique minimal pair in its equivalence class.     

Poisson polyhedra in high dimensions

The zero cell of a parametric class of random hyperplane tessellations depending on a distance exponent and an intensity parameter is investigated, as the space dimension tends to infinity. The model includes the zero cell of stationary and isotropic Poisson hyperplane tessellations as well as the typical cell of a stationary Poisson Voronoi tessellation as special cases. It is shown that asymptotically in the space dimension, with overwhelming probability these cells satisfy the hyperplane conjecture, if the distance exponent and the intensity parameter are suitably chosen dimension-dependent functions. Also the high dimensional limits of the mean number of faces are explored and the asymptotic behaviour of an isoperimetric ratio is analysed. In the background are new identities linking the f-vector of the zero cell to certain dual intrinsic volumes.     

All 0–1 polytopes are traveling salesman polytopes

We study the facial structure of two important permutation polytopes in , theBirkhoff orassignment polytopeB _n , defined as the convex hull of alln×n permutation matrices, and theasymmetric traveling salesman polytopeT _n , defined as the convex hull of thosen×n permutation matrices corresponding ton-cycles. Using an isomorphism between the face lattice ofB _n and the lattice of elementary bipartite graphs, we show, for example, that every pair of vertices ofB _n is contained in a cubical face, showing faces ofB _n to be fairly special 0–1 polytopes. On the other hand, we show thatevery 0–1d-polytope is affinely equivalent to a face ofT _n , fordlogn, by showing that every 0–1d-polytope is affinely equivalent to the asymmetric traveling salesman polytope of some directed graph withn nodes. The latter class of polytopes is shown to have maximum diameter [n/3].Partially supported by NSF grant DMS-9207700.     

Coxeter complexes and graph-associahedra

Given a graph Γ, we construct a simple, convex polytope, dubbed graph-associahedra, whose face poset is based on the connected subgraphs of Γ. This provides a natural generalization of the Stasheff associahedron and the Bott-Taubes cyclohedron. Moreover, we show that for any simplicial Coxeter system, the minimal blow-ups of its associated Coxeter complex has a tiling by graph-associahedra. The geometric and combinatorial properties of the complex as well as of the polyhedra are given. These spaces are natural generalizations of the Deligne-Knudsen-Mumford compactification of the real moduli space of curves.     

Orbit equivalence of Cantor minimal systems: A survey and a new proof

We give a new proof of the classification, up to topological orbit equivalence, of minimal AF-equivalence relations and minimal actions of the group of integers on the Cantor set. This proof relies heavily on the structure of AF-equivalence relations and the theory of dimension groups; we give a short survey of these topics.     

Higher integrality conditions, volumes and Ehrhart polynomials

A polytope is integral if all of its vertices are lattice points. The constant term of the Ehrhart polynomial of an integral polytope is known to be 1. In previous work, we showed that the coefficients of the Ehrhart polynomial of a lattice-face polytope are volumes of projections of the polytope. We generalize both results by introducing a notion of k-integral polytopes, where 0-integral is equivalent to integral. We show that the Ehrhart polynomial of a k-integral polytope P has the properties that the coefficients in degrees less than or equal to k are determined by a projection of P, and the coefficients in higher degrees are determined by slices of P. A key step of the proof is that under certain generality conditions, the volume of a polytope is equal to the sum of volumes of slices of the polytope.     

Semigroup of matrices acting on the max-plus projective space

We investigate the action of semigroups of d×d matrices with entries in the max-plus semifield on the max-plus projective space. Recall that semigroups generated by one element with projectively bounded image are projectively finite and thus contain idempotent elements.In terms of orbits, our main result states that the image of a minimal orbit by an idempotent element of the semigroup with minimal rank has at most d! elements. Moreover, each idempotent element with minimal rank maps at least one orbit onto a singleton.This allows us to deduce the central limit theorem for stochastic recurrent sequences driven by independent random matrices that take countably many values, as soon as the semigroup generated by the values contains an element with projectively bounded image.     

Moebius geometry of submanifolds in ? n

In this paper we define a Moebius invariant metric and a Moebius invariant second fundamental form for submanifolds in ? ⁿ and show that in case of a hypersurface with n≥ 4 they determine the hypersurface up to Moebius transformations. Using these Moebius invariants we calculate the first variation of the moebius volume functional. We show that any minimal surface in ? ⁿ is also Moebius minimal and that the image in ? ⁿ of any minimal surface in ℝ ⁿ unter the inverse of a stereographic projection is also Moebius minimal. Finally we use the relations between Moebius invariants to classify all surfaces in ?³ with vanishing Moebius form. Received: 18 November 1997     

An ‘odd’ formula for the volume of three-dimensional lattice polyhedra

Let be the tiling of R ³ with unit cubes whose vertices belong to the fundamental lattice L ₁ of points with integer coordinates. Denote by L _n the lattice consisting of all points x in R ³ such that nx belongs to L ₁. When the vertices of a polyhedron P in R ³ are restricted to lie in L ₁ then there is a formula which relates the volume of P to the numbers of all points of two lattices L ₁ and L _n lying in the interior and on the boundary of P. In the simplest case of the lattices L ₁ and L ₂ there are 27 points in each cube from whose relationships to the polyhedron P must be examined. In this note we present a new formula for the volume of lattice polyhedra in R ³ which involves only nine points in each cube of : one from L ₂ and eight belonging to L ₄. Another virtue of our formula is that it does not employ any additional parameters, such as the Euler characteristic.     

Families of Tight Inequalities for Polytopes

We use the Billera-Liu algebra to show how the flag f-vectors of several special classes of polytopes fit into the closed convex hull of the flag f-vectors of all polytopes. In particular, we describe inequalities that define the faces of the closed convex hull of the flag f-vectors of all d-polytopes that are spanned by the flag f-vectors of simplicial, simple, k-simplicial, and k-simple d-polytopes. We also describe inequalities that define the face of the closed convex hull of the flag f-vectors of all d-zonotopes spanned by the flag f-vectors of cubical d-zonotopes, and give an upper bound on the dimension of the span of the flag f-vectors of k-cubical zonotopes. Finally, we strengthen some previously known inequalities for flag f-vectors of zonotopes.     

Finding Optimal Shadows of Polytopes

This paper deals with the problem of projecting polytopes in finite-dimensional Euclidean spaces on subspaces of given dimension so as to maximize or minimize the volume of the projection. As to the computational complexity of the underlying decision problems we show that maximizing the volume of the orthogonal projection on hyperplanes is already NP-hard for simplices. For minimization, the problem is easy for simplices but NP-hard for bipyramids over parallelotopes. Similar results are given for projections on lower-dimensional subspaces. Several other related NP-hardness results are also proved including one for inradius computation of zonotopes and another for a location problem. On the positive side, we present various polynomial-time approximation algorithms. In particular, we give a randomized algorithm for maximizing orthogonal projections of CH-polytopes in R ⁿ on hyperplanes with an error bound of essentially . Received February 17, 1999.     

On the cube problem of Las Vergnas

We prove a conjecture of Las Vergnas in dimensions d7: The matroid of the d-dimensional cube C ^d has a unique reorientation class. This extends a result of Las Vergnas, Roudneff and Salaün in dimension 4. Moreover, we determine the automorphism group G ^d of the matroid of the d-cube C ^d for arbitrary dimension d, and we discuss its relation to the Coxeter group of C ^d . We introduce matroid facets of the matroid of the d-cube in order to evaluate the order of G ^d . These matroid facets turn out to be arbitrary pairs of parallel subfacets of the cube. We show that the Euclidean automorphism group W ^d is a proper subgroup of the group G ^d of all matroid symmetries of the d-cube by describing genuine matroid symmetries for each Euclidean facet. A main theorem asserts that any one of these matroid symmetries together with the Euclidean Coxeter symmetries generate the full automorphism group G ^d . For the proof of Las Vergnas' conjecture we use essentially these symmetry results together with the fact that the reorientation class of an oriented matroid is determined by the labeled lower rank contractions of the oriented matroid. We also describe the Folkman-Lawrence representation of the vertex figure of the d-cube and a contraction of it. Finally, we apply our method of proof to show a result of Las Vergnas, Roudneff, and Salaün that the matroid of the 24-cell has a unique reorientation class, too.