Polytopality and Cartesian products of graphs

We study the question of polytopality of graphs: when is a given graph the graph of a polytope? We first review the known necessary conditions for a graph to be polytopal, and we present three families of graphs which satisfy all these conditions, but which nonetheless are not graphs of polytopes. Our main contribution concerns the polytopality of Cartesian products of non-polytopal graphs. On the one hand, we show that products of simple polytopes are the only simple polytopes whose graph is a product. On the other hand, we provide a general method to construct (non-simple) polytopal products whose factors are not polytopal.     

Which nonnegative matrices are slack matrices?

In this paper we characterize the slack matrices of cones and polytopes among all nonnegative matrices. This leads to an algorithm for deciding whether a given matrix is a slack matrix. The underlying decision problem is equivalent to the polyhedral verification problem whose complexity is unknown.     

Gal’s conjecture for nestohedra corresponding to complete bipartite graphs

Convex polytopes have interested mathematicians since very ancient times. At present, they occupy a central place in convex geometry, combinatorics, and toric topology and demonstrate the harmony and beauty of mathematics. This paper considers the problem of describing the f-vectors of simple flag polytopes, that is, simple polytopes in which any set of pairwise intersecting facets has nonempty intersection. We show that for each nestohedron corresponding to a connected building set, the h-polynomial is a descent-generating function for some class of permutations; we also prove Gal’s conjecture on the nonnegativity of γ-vectors of flag polytopes for nestohedra constructed over complete bipartite graphs.     

Multivariate splines and polytopes

In this paper, we use multivariate splines to investigate the volume of polytopes. We first present an explicit formula for the multivariate truncated power, which can be considered as a dual version of the famous Brion’s formula for the volume of polytopes. We also prove that the integration of polynomials over polytopes can be dealt with by using the multivariate truncated power. Moreover, we show that the volume of cube slicing can be considered as the maximum value of the box spline. On the basis of this connection, we give a simple proof for Good’s conjecture, which has been settled before by probability methods.     

On toric h-vectors of centrally symmetric polytopes

We prove tight lower bounds for the coefficients of the toric h-vector of an arbitrary centrally symmetric polytope generalizing previous results due to R. Stanley and the author using toric varieties. Our proof here is based on the theory of combinatorial intersection cohomology for normal fans of polytopes developed by G. Barthel, J.-P. Brasselet, K. Fieseler and L. Kaup, and independently by P. Bressler and V. Lunts. This theory is also valid for nonrational polytopes when there is no standard correspondence with toric varieties. In this way we can establish our bounds for centrally symmetric polytopes even without requiring them to be rational. Received: 24 March 2004     

An application of Guillemin-Abreu theory to a non-abelian group action

This note is a step towards demonstrating the benefits of a symplectic approach to studying equivariant Kähler geometry. We apply a local differential geometric framework from Kähler toric geometry due to Guillemin and Abreu to the case of the standard linear SU(n) action on Cn?{0}. Using this framework we (re)construct certain Kähler metrics from data on moment polytopes.     

Alcoved Polytopes,I

The aim of this paper is to study alcoved polytopes, which are polytopes arising from affine Coxeter arrangements. This class of convex polytopes includes many classical polytopes, for example, the hypersimplices. We compare two constructions of triangulations of hypersimplices due to Stanley and Sturmfels and explain them in terms of alcoved polytopes. We study triangulations of alcoved polytopes, the adjacency graphs of these triangulations, and give a combinatorial formula for volumes of these polytopes. In particular, we study a class of matroid polytopes, which we call the multi-hypersimplices.     

Algebro-geometric characterization of Cayley polytopes

In this paper, we give an algebro-geometric characterization of Cayley polytopes. As a special case, we also characterize lattice polytopes with lattice width one by using Seshadri constants.     

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.     

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.     

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.     

Puzzles and polytope isomorphisms

We show that an isomorphism between the graphs of two simple polytopes of arbitrary dimension can always be extended to an isomorphism between the polytopes themselves. It has been convenient to study the dual situation, involving what we like to call the puzzle of a simplicial polytope.Dedicated to Professor Otto Haupt with best wishes on his 100th birthday.     

Generalized 1-Skeleta and a Lifting Result

Guillemin and Zara (Duke Math J 107(2):283–349, 2001) described an analogue of Morse theory on a certain class of 1-skeleta including all those coming from simple polytopes. In this paper we extend the methods of Guillemin and Zara to a larger class of 1-skeleta including all those coming from simple polytopes and their 1-skeleton projections. As an application of these methods we prove a lifting result which yields an intrinsic characterization of 1-skeleton projections of simple polytopes.     

A generalization of antiwebs to independence systems and their canonical facets

We consider independence system polytopes, i.e. polytopes whose extreme points are the incidence vectors of the sets of an independence system. We first give a sufficient condition for recognizing Boolean facets. Then, the notion of antiweb introduced by Trotter for graphs is generalized to independence systems and used for obtaining canonical facets of the associated polytopes. We also point out how our results relate with known ones for knapsack, set covering and matroid polytopes.     

On Gale and braxial polytopes

Cyclic polytopes are characterized as simplicial polytopes satisfying Gale’s evenness condition (a combinatorial condition on facets relative to a fixed ordering of the vertices). Periodically-cyclic polytopes are polytopes for which certain subpolytopes are cyclic. Bisztriczky discovered a class of periodically-cyclic polytopes that also satisfy Gale’s evenness condition. The faces of these polytopes are braxtopes, a certain class of nonsimplicial polytopes studied by the authors. In this paper we prove that the periodically-cyclic Gale polytopes of Bisztriczky are exactly the polytopes that satisfy Gale’s evenness condition and are braxial (all faces are braxtopes). The existence of other periodically-cyclic Gale polytopes is open. Supported in part by a grant from the University of Kansas General Research Fund and by a Natural Sciences and Engineering Research Council of Canada Discovery Grant. Received: 20 September 2006     

Linear programming, the simplex algorithm and simple polytopes

In the first part of the paper we survey some far-reaching applications of the basic facts of linear programming to the combinatorial theory of simple polytopes. In the second part we discuss some recent developments concerning the simplex algorithm. We describe subexponential randomized pivot rules and upper bounds on the diameter of graphs of polytopes. © 1997 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Cohomological rigidity and the number of homeomorphism types for small covers over prisms

In this paper, based upon the basic theory for glued manifolds in M.W. Hirsch (1976) [8, Chapter 8, §2 Gluing Manifolds Together], we give a method of constructing homeomorphisms between two small covers over simple convex polytopes. As a result we classify, up to homeomorphism, all small covers over a 3-dimensional prism P³(m) with m?3. We introduce two invariants from colored prisms and other two invariants from ordinary cohomology rings with Z₂-coefficients of small covers. These invariants can form a complete invariant system of homeomorphism types of all small covers over a prism in most cases. Then we show that the cohomological rigidity holds for all small covers over a prism P³(m) (i.e., cohomology rings with Z₂-coefficients of all small covers over a P³(m) determine their homeomorphism types). In addition, we also calculate the number of homeomorphism types of all small covers over P³(m).