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.     

h-Vectors of Gorenstein polytopes

We show that the Ehrhart h-vector of an integer Gorenstein polytope with a regular unimodular triangulation satisfies McMullen's g-theorem; in particular, it is unimodal. This result generalizes a recent theorem of Athanasiadis (conjectured by Stanley) for compressed polytopes. It is derived from a more general theorem on Gorenstein affine normal monoids M: one can factor K[M] (K a field) by a “long” regular sequence in such a way that the quotient is still a normal affine monoid algebra. This technique reduces all questions about the Ehrhart h-vector of P to the Ehrhart h-vector of a Gorenstein polytope Q with exactly one interior lattice point, provided each lattice point in a multiple cP, c∈N, can be written as the sum of c lattice points in P. (Up to a translation, the polytope Q belongs to the class of reflexive polytopes considered in connection with mirror symmetry.) If P has a regular unimodular triangulation, then it follows readily that the Ehrhart h-vector of P coincides with the combinatorial h-vector of the boundary complex of a simplicial polytope, and the g-theorem applies.     

Bigraded Betti numbers of certain simple polytopes

The bigraded Betti numbers β ^?i,2j (P) of a simple polytope P are the dimensions of the bigraded components of the Tor groups of the face ring k[P]. The numbers β ^?i,2j (P) reflect the combinatorial structure of P, as well as the topological structure of the corresponding moment-angle manifold Z _P ; thus, they find numerous applications in combinatorial commutative algebra and toric topology. We calculate certain bigraded Betti numbers of the type β ^?i,2(i+1) for associahedra and apply the calculation of bigraded Betti numbers for truncation polytopes to study the topology of their moment-angle manifolds. Presumably, for these two series of simple polytopes, the numbers β ^?i,2j (P) attain their minimum and maximum values among all simple polytopes P of fixed dimension with a given number of facets.     

Lattice polytopes,Hecke operators,and the Ehrhart polynomial

Let P be a simple lattice polytope. We define an action of the Hecke operators on E(P), the Ehrhart polynomial of P, and describe their effect on the coefficients of E(P). We also describe how the Brion–Vergne formula for E(P) transforms under the Hecke operators for nonsingular lattice polytopes P.      

f-Vectors of Minkowski Additions of Convex Polytopes

The objective of this paper is to present two types of results on Minkowski sums of convex polytopes. The first is about a special class of polytopes we call perfectly centered and the combinatorial properties of the Minkowski sum with their own dual. In particular, we have a characterization of the face lattice of the sum in terms of the face lattice of a given perfectly centered polytope. Exact face counting formulas are then obtained for perfectly centered simplices and hypercubes. The second type of results concerns tight upper bounds for the f-vectors of Minkowski sums of several polytopes.     

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.     

Colorful polytopes and graphs

The paper investigates connections between abstract polytopes and properly edge colored graphs. Given any finite n-edge-colored n-regular graph G, we associate to G a simple abstract polytope P _G of rank n, the colorful polytope of G, with 1-skeleton isomorphic to G. We investigate the interplay between the geometric, combinatorial, or algebraic properties of the polytope P _G and the combinatorial or algebraic structure of the underlying graph G, focussing in particular on aspects of symmetry. Several such families of colorful polytopes are studied including examples derived from a Cayley graph, in particular the graphicahedra, as well as the flagadjacency polytopes and related monodromy polytopes associated with a given abstract polytope. The duals of certain families of colorful polytopes have been important in the topological study of colored triangulations and crystallization of manifolds.     

On locally spherical polytopes of type {5, 3, 5}

There are only finitely many locally projective regular polytopes of type {5, 3, 5}. They are covered by a locally spherical polytope whose automorphism group is J₁×J₁×L₂(19), where J₁ is the first Janko group, of order 175560, and L₂(19) is the projective special linear group of order 3420. This polytope is minimal, in the sense that any other polytope that covers all locally projective polytopes of type {5, 3, 5} must in turn cover this one.     

Fractional Power Series Solutions for Systems of Equations

Abstract. In this paper we extend the explorations in [8] to include the fractional power series expansions of k equations in d variables, where d>k . An analog of Newton's polygon construction which uses the Minkowski sum P of the Newton polytopes P ₁ ,...,P _k of the k equations is given for computing such series expansions. If the Newton polytopes of these equations are the same, then the common domains of convergence for the solutions correspond to the vertices of a certain fiber polytope Σ(P) . In general, our results suggest the existence of a ``mixed fiber polytope' of k polytopes. It is also indicated that there may be a relationship between these mixed fiber polytopes and a generalization of the discriminant, which we call the mixed discriminant.     

Intersecting all edges of convex polytopes by planes

A characterization theorem is given for 3-dimensional convex polytopes Q having the following property: There exists a polytope P, isomorphic to Q, all edges of which can be cut by a pair of planes that miss all its vertices. The result yields an affirmative solution of a conjecture of B. Grünbaum.     

Some representations of solutions of elliptic equations

The Dirichlet problem for the region of the plane inside closed smooth curve C for second-order elliptic equations is considered. It is shown that under certain circumstances the solution u can be written uniquely in the form u(P) = ∝_cF(P, Q) g(Q) ds_Q, where F(P, Q) is the fundamental solution of the elliptic equation, and g?L² if the boundary value function f is absolutely continuous with square integrable derivative (f?W); and u(P) = p(F(P, ·)) where p is a unique bounded linear functional on W if f?L². These representations are valid in the exterior of C also. As special cases with slight modifications, the exterior Dirichlet problems for the Helmholtz and Laplace equations are mentioned.It is shown also that if kernel F(P′, Q), with P′ and Q on C, has a complete set of eigenfunctions {ψ_k(P′)} then u(P) can be expanded in a series of their extensions {ψ_k(P)}, where ψ_k(P) = λ_k ∝_cF(P, Q) ψ_k(Q) ds_Q.     

Centrally symmetric polytopes with many faces

We present explicit constructions of centrally symmetric polytopes with many faces: (1) we construct a d-dimensional centrally symmetric polytope P with about 3 ^d/4 ≈ (1.316) ^d vertices such that every pair of non-antipodal vertices of P spans an edge of P, (2) for an integer k ≥ 2, we construct a d-dimensional centrally symmetric polytope P of an arbitrarily high dimension d and with an arbitrarily large number N of vertices such that for some 0 < δ _k < 1 at least (1 ? (δ _k ) ^d )( _k ^N ) k-subsets of the set of vertices span faces of P, and (3) for an integer k ≥ 2 and α > 0, we construct a centrally symmetric polytope Q with an arbitrarily large number of vertices N and of dimension d = k ^1+o(1) such that at least $(1 - k^{ - \alpha } )(_k^N )$ k-subsets of the set of vertices span faces of Q.     

On the Connection Between the Projection and the Extension of a Parallelotope

This paper presents a result concerning the connection between the parallel projection P _v,H of a parallelotope P along the direction v (into a transversal hyperplane H) and the extension P + S(v), meaning the Minkowski sum of P and the segment S(v) = {λv | −1 ≤ λ ≤ 1}. A sublattice L _v of the lattice of translations of P associated to the direction v is defined. It is proved that the extension P + S(v) is a parallelotope if and only if the parallel projection P _v,H is a parallelotope with respect to the lattice of translations L _v,H , which is the projection of the lattice L _v along the direction v into the hyperplane H.     

Linear Equations for the Number of Intervals Which are Isomorphic with Boolean Lattices and the Dehn–Sommerville Equations

Let P be a finite poset. Let L: = J(P) denote the lattice of order ideals of P. Let b _i (L) denote the number of Boolean intervals of L of rank i.

We construct a simple graph G(P) from our poset P. Denote by f _i (P) the number of the cliques K _i+1, contained in the graph G(P).

Our main results are some linear equations connecting the numbers f _i (P) and b _i (L).

We reprove the Dehn–Sommerville equations for simplicial polytopes.

In our proof, we use free resolutions and the theory of Stanley–Reisner rings.     

Graphs whose signless Laplacian spectral radius does not exceed the Hoffman limit value

For a graph matrix M, the Hoffman limit value H(M) is the limit (if it exists) of the largest eigenvalue (or, M-index, for short) of M(H_n), where the graph H_n is obtained by attaching a pendant edge to the cycle C_n-1 of length n-1. In spectral graph theory, M is usually either the adjacency matrix A or the Laplacian matrix L or the signless Laplacian matrix Q. The exact values of H(A) and H(L) were first determined by Hoffman and Guo, respectively. Since H_n is bipartite for odd n, we have H(Q)=H(L). All graphs whose A-index is not greater than H(A) were completely described in the literature. In the present paper, we determine all graphs whose Q-index does not exceed H(Q). The results obtained are determinant to describe all graphs whose L-index is not greater then H(L). This is done precisely in Wang et al. (in press) [21].     

The Flag Polynomial of the Minkowski Sum of Simplices

For a polytope we define the flag polynomial, a polynomial in commuting variables related to the well-known flag vector and describe how to express the flag polynomial of the Minkowski sum of k standard simplices in a direct and canonical way in terms of the k-th master polytope P(k) where ${k \in \mathbb {N}}$ . The flag polynomial facilitates many direct computations. To demonstrate this we provide two examples; we first derive a formula for the f -polynomial and the maximum number of d-dimensional faces of the Minkowski sum of two simplices. We then compute the maximum discrepancy between the number of (0, d)-chains of faces of a Minkowski sum of two simplices and the number of such chains of faces of a simple polytope of the same dimension and on the same number of vertices.     

On the Hardness of Computing Intersection,Union and Minkowski Sum of Polytopes

For polytopes P ₁,P ₂⊂ℝ ^d , we consider the intersection P ₁∩P ₂, the convex hull of the union CH(P ₁∪P ₂), and the Minkowski sum P ₁+P ₂. For the Minkowski sum, we prove that enumerating the facets of P ₁+P ₂ is NP-hard if P ₁ and P ₂ are specified by facets, or if P ₁ is specified by vertices and P ₂ is a polyhedral cone specified by facets. For the intersection, we prove that computing the facets or the vertices of the intersection of two polytopes is NP-hard if one of them is given by vertices and the other by facets. Also, computing the vertices of the intersection of two polytopes given by vertices is shown to be NP-hard. Analogous results for computing the convex hull of the union of two polytopes follow from polar duality. All of the hardness results are established by showing that the appropriate decision version, for each of these problems, is NP-complete.     

The automorphism group of a function lattice: A problem of Jónsson and McKenzie

It is shown that Aut(L ^Q ) is naturally isomorphic to Aut(L) × Aut(Q) whenL is a directly and exponentially indecomposable lattice,Q a non-empty connected poset, and one of the following holds:Q is arbitrary butL is ajm-lattice,Q is finitely factorable and L is complete with a join-dense subset of completely join-irreducible elements, orL is arbitrary butQ is finite. A problem of Jónsson and McKenzie is thereby solved. Sharp conditions are found guaranteeing the injectivity of the natural mapv _P,Q from Aut(P) × Aut(Q) to Aut(P ^Q )P andQ posets), correcting misstatements made by previous authors. It is proven that, for a bounded posetP and arbitraryQ, the Dedekind-MacNeille completion ofP ^Q ,DM(P ^Q ), is isomorphic toDM(P)^Q. This isomorphism is used to prove that the natural mapv _P,Q is an isomorphism ifv _DM(P),Q is, reducing a poset problem to a more tractable lattice problem.Presented by B. Jonsson.The author would like to thank his supervisor, Dr. H. A. Priestley, for her direction and advice as well as his undergraduate supervisor, Prof. Garrett Birkhoff, and Dr. P. M. Neumann for comments regarding the paper. This material is based upon work supported under a (U.S.) National Science Foundation Graduate Research Fellowship and a Marshall Aid Commemoration Commission Scholarship.     

Gorenstein polytopes and their stringy E-functions

Inspired by ideas from algebraic geometry, Batyrev and the first named author have introduced the stringy E-function of a Gorenstein polytope. We prove that this a priori rational function is actually a polynomial, which is part of a conjecture of Batyrev and the first named author. The proof relies on a comparison result for the lattice point structure of a Gorenstein polytope P, a face F of P and the face of the dual Gorenstein polytope corresponding to F. In addition, we study joins of Gorenstein polytopes and introduce the notion of an irreducible Gorenstein polytope. We show how these concepts relate to the decomposition of nef-partitions.