Valuations on lattice polytopes

Let L be a lattice (that is, a Z-module of finite rank), and let L=P(L) denote the family of convex polytopes with vertices in L; here, convexity refers to the underlying rational vector space V=Q⊗L. In this paper it is shown that any valuation on L satisfies the inclusion-exclusion principle, in the strong sense that appropriate extension properties of the valuation hold. Indeed, the core result is that the class of a lattice polytope in the abstract group L=P(L) for valuations on L can be identified with its characteristic function in V. In fact, the same arguments are shown to apply to P(M), when M is a module of finite rank over an ordered ring, and more generally to appropriate families of (not necessarily bounded) polyhedra.     

Lattice-free polytopes and their diameter

A convex polytope in real Euclidean space islattice-free if it intersects some lattice in space exactly in its vertex set. Lattice-free polytopes form a large and computationally hard class, and arise in many combinatorial and algorithmic contexts. In this article, affine and combinatorial properties of such polytopes are studied. First, bounds on some invariants, such as the diameter and layer-number, are given. It is shown that the diameter of ad-dimensional lattice-free polytope isO(d ³). A bound ofO(nd+d ³) on the diameter of ad-polytope withn facets is deduced for a large class of integer polytopes. Second, Delaunay polytopes and [0, 1]-polytopes, which form major subclasses of lattice-free polytopes, are considered. It is shown that, up to affine equivalence, for anyd≥3 there are infinitely manyd-dimensional lattice-free polytopes but only finitely many Delaunay and [0, 1]-polytopes. Combinatorial-types of lattice-free polytopes are discussed, and the inclusion relations among the subclasses above are examined. It is shown that the classes of combinatorial-types of Delaunay polytopes and [0,1]-polytopes are mutually incomparable starting in dimension six, and that both are strictly contained in the class of combinatorial-types of all lattice-free polytopes. This research was supported by DIMACS—the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers University.     

Lattice points in lattice polytopes

IfK is the underlying point-set of a simplicial complex of dimension at mostd whose vertices are lattice points, and ifG(K) is the number of lattice points inK, then the lattice point enumeratorG(K,t)=1+ _n1 G(nK)t ⁿ takes the formC(K, t)/(1–t) ^d+1, for some polynomialC(K, t). Here,C(K, t) is expressed as a sum of local terms, one for each face ofK. WhenK is a polytope or its boundary, there result inequalities between the numbersG _r (K), whereG(n K)= _r=0 ^d n ^r G _r (K).     

Distance between vertices of lattice polytopes

Optimization Letters - A lattice (d,k)-polytope is the convex hull of a set of points in dimension d whose coordinates are integers ranging between 0 and k. We consider the largest possible...     

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).     

Some upper bounds for the diameters of convex polytopes

Δ(d, n) is defined to be the maximum diameter of ad-polytope withn-facets. The main results of the work are an evaluation of Δ(4, 10) and Δ(5, 11). Also, improved upper bounds are found for Δ(6, 13) and Δ(7,14).     

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.     

Recent progress on the combinatorial diameter of polytopes and simplicial complexes

The Hirsch Conjecture, posed in 1957, stated that the graph of a d-dimensional polytope or polyhedron with n facets cannot have diameter greater than n?d. The conjecture itself has been disproved, but what we know about the underlying question is quite scarce. Most notably, no polynomial upper bound is known for the diameters that were conjectured to be linear. In contrast, no polyhedron violating the conjecture by more than 25 % is known. This paper reviews several recent attempts and progress on the question. Some work is in the world of polyhedra or (more often) bounded polytopes, but some try to shed light on the question by generalizing it to simplicial complexes. In particular, we include here our recent and previously unpublished proof that the maximum diameter of arbitrary simplicial complexes is in n ^Θ(d), and we summarize the main ideas in the polymath 3 project, a web-based collective effort trying to prove an upper bound of type nd for the diameters of polyhedra and of more general objects (including, e.g., simplicial manifolds).     

Notes on lattice points of zonotopes and lattice-face polytopes

Minkowski’s second theorem on successive minima gives an upper bound on the volume of a convex body in terms of its successive minima. We study the problem to generalize Minkowski’s bound by replacing the volume by the lattice point enumerator of a convex body. In this context we are interested in bounds on the coefficients of Ehrhart polynomials of lattice polytopes via the successive minima. Our results for lattice zonotopes and lattice-face polytopes imply, in particular, that for 0-symmetric lattice-face polytopes and lattice parallelepipeds the volume can be replaced by the lattice point enumerator.     

Facial structures of lattice path matroid polytopes

A lattice path matroid is a transversal matroid corresponding to a pair of lattice paths on the plane. A matroid base polytope is the polytope whose vertices are the incidence vectors of the bases of the given matroid. In this paper, we study the facial structures of matroid base polytopes corresponding to lattice path matroids. In the case of a border strip, we show that all faces of a lattice path matroid polytope can be described by certain subsets of deletions, contractions, and direct sums. In particular, we express them in terms of the lattice path obtained from the border strip. Subsequently, the facial structures of a lattice path matroid polytope for a general case are explained in terms of certain tilings of skew shapes inside the given region.     

Upper bounds for configurations and polytopes inR d

We give a new upper bound onn ^d(d+1)n on the number of realizable order types of simple configurations ofn points inR ^d , and ofn2d ² n on the number of realizable combinatorial types of simple configurations. It follows as a corollary of the first result that there are no more thann ^d(d+1)n combinatorially distinct labeled simplicial polytopes inR ^d withn vertices, which improves the best previous upper bound ofn ^{cn d/2}.Supported in part by NSF Grant DMS-8501492 and PSC-CUNY Grant 665258.Supported in part by NSF Grant DMS-8501947.     

Classifying smooth lattice polytopes via toric fibrations

We show that any smooth Q-normal lattice polytope P of dimension n and degree d is a strict Cayley polytope if n?2d+1. This gives a sharp answer, for this class of polytopes, to a question raised by V.V. Batyrev and B. Nill.     

Sharper bounds on four lattice constants

Designs, Codes and Cryptography - The Korkine–Zolotareff (KZ) reduction and its generalisations, are widely used lattice reduction strategies in communications and cryptography. The KZ...     

On the diameter of partition polytopes and vertex-disjoint cycle cover

We study the combinatorial diameter of partition polytopes, a special class of transportation polytopes. They are associated to partitions of a set X = {x ₁, . . . , x _n } of items into clusters C ₁, . . . , C _k of prescribed sizes κ ₁ ≥ · · · ≥ κ _k . We derive upper bounds on the diameter in the form of κ ₁ + κ ₂, n ? κ ₁ and ${\lfloor \frac{n}{2} \rfloor}$ . This is a direct generalization of the diameter-2 result for the Birkhoff polytope. The bounds are established using a constructive, graph-theoretical approach where we show that special sets of vertices in graphs that decompose into cycles can be covered by a set of vertex-disjoint cycles. Further, we give exact diameters for partition polytopes with k = 2 or k = 3 and prove that, for all k ≥ 4 and all κ ₁, κ ₂, there are cluster sizes κ ₃, . . . , κ _k such that the diameter of the corresponding partition polytope is at least ${\lceil \frac{4}{3} \kappa_2 \rceil}$ . Finally, we provide an ${O(n(\kappa_1 + \kappa_2(\sqrt{k} - 1)))}$ algorithm for an edge-walk connecting two given vertices of a partition polytope that also adheres to our diameter bounds.     

Improved bounds on the supremum of autoconvolutions

We give an improvement of the best known lower bound for the supremum of autoconvolutions of nonnegative functions supported in a compact interval. Also, by means of explicit examples we disprove a long standing natural conjecture of Schinzel and Schmidt concerning the extremal function for such autoconvolutions.     

Correction to: Distance between vertices of lattice polytopes

Optimization Letters - The erratum mostly concerns Table 4 and Figure 6 where two polytopes were misrepresented in the original version.