An exploration of locally projective polytopes

This article completes the classification of finite universal locally projective regular abstract polytopes, by summarising (with careful references) previously published results on the topic, and resolving the few cases that do not appear in the literature. In rank 4, all quotients of the locally projective polytopes are also noted. In addition, the article almost completes the classification of the infinite universal locally projective polytopes, except for the {{5,3,3,},{3,3,5}₁₅} and its dual. It is shown that this polytope cannot be finite, but its existence is not established. The most remarkable feature of the classification is that a nondegenerate universal locally projective polytope is infinite if and only if the rank of is 5 and the facets of or its dual are the hemi-120-cell {5,3,3}₁₅.     

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.     

Quotients of Some Finite Universal Locally Projective Polytopes

   Abstract. This paper classifies the quotients of a finite and locally projective polytope of type {4,3,5} . Seventy quotients are found, including three regular polytopes, and nine other section regular polytopes which are themselves locally projective. The classification is done with the assistance of GAP, a computer system for algebraic computation. The same techniques are also applied to two finite locally projective polytopes respectively of type {3,5,3} and {5,3,5} . No nontrivial quotients of the latter are found.     

Quotients of Some Finite Universal Locally Projective Polytopes

Abstract. This paper classifies the quotients of a finite and locally projective polytope of type {4,3,5} . Seventy quotients are found, including three regular polytopes, and nine other section regular polytopes which are themselves locally projective. The classification is done with the assistance of GAP, a computer system for algebraic computation. The same techniques are also applied to two finite locally projective polytopes respectively of type {3,5,3} and {5,3,5} . No nontrivial quotients of the latter are found.     

Gelfand-Tsetlin polytopes and Feigin-Fourier-Littelmann-Vinberg polytopes as marked poset polytopes

Stanley (1986) showed how a finite partially ordered set gives rise to two polytopes, called the order polytope and chain polytope, which have the same Ehrhart polynomial despite being quite different combinatorially. We generalize his result to a wider family of polytopes constructed from a poset P with integers assigned to some of its elements.Through this construction, we explain combinatorially the relationship between the Gelfand-Tsetlin polytopes (1950) and the Feigin-Fourier-Littelmann-Vinberg polytopes (2010, 2005), which arise in the representation theory of the special linear Lie algebra. We then use the generalized Gelfand-Tsetlin polytopes of Berenstein and Zelevinsky (1989) to propose conjectural analogues of the Feigin-Fourier-Littelmann-Vinberg polytopes corresponding to the symplectic and odd orthogonal Lie algebras.     

Facets and volume of Gorenstein Fano polytopes

It is known that every integral convex polytope is unimodularly equivalent to a face of some Gorenstein Fano polytope. It is then reasonable to ask whether every normal polytope is unimodularly equivalent to a face of some normal Gorenstein Fano polytope. In the present paper, it is shown that, by giving new classes of normal Gorenstein Fano polytopes, each order polytope as well as each chain polytope of dimension d is unimodularly equivalent to a facet of some normal Gorenstein Fano polytopes of dimension . Furthermore, investigation on combinatorial properties, especially, Ehrhart polynomials and volume of these new polytopes will be achieved. Finally, some curious examples of Gorenstein Fano polytopes will be discovered.     

Polyhedral combinatorics of multi-index axial transportation problems

This paper studies integer points (IP) and integer vertices (IV) of the p-index axial transportation polytope (p  -ATP) of order _n1×_n2×?×_np$n_1\times n_2\times ?\times n_p$, _n1,_n2,…,_np?2$n_1\text{,}{n}_2\text{,}\dots \text{,}{n}_p?2$, p?2$p?2$, defined by integer vectors, as well as noninteger vertices of the 3-ATP. In particular, for the p  -ATP, we establish criteria for the minimum and maximum number of IPs and describe the class of polytopes for which the number of IPs coincides with the number of IVs. For the 3-ATP of order n×n×n$n\times n\times n$, we prove the theorem on the exponential growth of denominators of fractional components of the polytope vertices. Three conjectures are stated regarding the maximum number of vertices of the p-ATP, the maximum number of IVs, and the structure of the nondegenerate polytopes with the maximum number of IPs.     

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.     

Minkowski Length of 3D Lattice Polytopes

We study the Minkowski length L(P) of a lattice polytope P, which is defined to be the largest number of non-trivial primitive segments whose Minkowski sum lies in P. The Minkowski length represents the largest possible number of factors in a factorization of polynomials with exponent vectors in P, and shows up in lower bounds for the minimum distance of toric codes. In this paper we give a polytime algorithm for computing L(P) where P is a 3D lattice polytope. We next study 3D lattice polytopes of Minkowski length 1. In particular, we show that if Q, a subpolytope of P, is the Minkowski sum of L=L(P) lattice polytopes Q _i , each of Minkowski length 1, then the total number of interior lattice points of the polytopes Q ₁,??,Q _L is at most 4. Both results extend previously known results for lattice polygons. Our methods differ substantially from those used in the two-dimensional case.     

Unions of Fat Convex Polytopes Have Short Skeletons

The skeleton of a polyhedral set is the union of its edges and vertices. Let \(\mathcal {P}\) be a set of fat, convex polytopes in three dimensions with n vertices in total, and let f _max be the maximum complexity of any face of a polytope in \(\mathcal {P}\). We prove that the total length of the skeleton of the union of the polytopes in \(\mathcal {P}\) is at most O(α(n)?log^? n?logf _max) times the sum of the skeleton lengths of the individual polytopes.     

Locally projective polytopes of type

This paper attempts to classify the locally projective section regular n-polytopes of type {4,3,…,3,p}, that is, to classify polytopes whose facets are cubes or hemicubes, and the vertex figures are spherical or projective polytopes of type {3,…,3,p}, with the facets and vertex figures being not both spherical. Spherical or projective (n−1)-polytopes of type {3,…,3,p} only exist when p4, or p=5 and n−14, or n−1=2. However, some existence and non-existence results are obtained for other values of p and n. In particular, a link is derived between the existence of polytopes of certain types, and vertex-colourability of certain graphs. The main result of the paper is that locally projective section regular n-polytopes exist only when p=4, or when p=5 and n=4 or 5.     

Roots of Ehrhart polynomials arising from graphs

Several polytopes arise from finite graphs. For edge and symmetric edge polytopes, in particular, exhaustive computation of the Ehrhart polynomials not merely supports the conjecture of Beck et al. that all roots α of Ehrhart polynomials of polytopes of dimension D satisfy −D≤Re(α)≤D−1, but also reveals some interesting phenomena for each type of polytope. Here we present two new conjectures: (1) the roots of the Ehrhart polynomial of an edge polytope for a complete multipartite graph of order d lie in the circle |z+\fracd4| ￡ \fracd4|z+\frac{d}{4}| \le \frac{d}{4} or are negative integers, and (2) a Gorenstein Fano polytope of dimension D has the roots of its Ehrhart polynomial in the narrower strip -\fracD2 ￡ Re(a) ￡ \fracD2-1-\frac{D}{2} \leq \mathrm{Re}(\alpha) \leq \frac{D}{2}-1. Some rigorous results to support them are obtained as well as for the original conjecture. The root distribution of Ehrhart polynomials of each type of polytope is plotted in figures.     

Ehrhart polynomials of lattice-face polytopes

There is a simple formula for the Ehrhart polynomial of a cyclic polytope. The purpose of this paper is to show that the same formula holds for a more general class of polytopes, lattice-face polytopes. We develop a way of decomposing any -dimensional simplex in general position into signed sets, each of which corresponds to a permutation in the symmetric group and reduce the problem of counting lattice points in a polytope in general position to that of counting lattice points in these special signed sets. Applying this decomposition to a lattice-face simplex, we obtain signed sets with special properties that allow us to count the number of lattice points inside them. We are thus able to conclude the desired formula for the Ehrhart polynomials of lattice-face polytopes.

     

Perturbation of transportation polytopes

We describe a perturbation method that can be used to reduce the problem of finding the multivariate generating function (MGF) of a non-simple polytope to computing the MGF of simple polytopes. We then construct a perturbation that works for any transportation polytope. We apply this perturbation to the family of central transportation polytopes of order $kn\times n$, and obtain formulas for the MGFs of the feasible cone of each vertex of the polytope and the MGF of the polytope. The formulas we obtain are enumerated by combinatorial objects. A special case of the formulas recovers the results on Birkhoff polytopes given by the author and De Loera and Yoshida. We also recover the formula for the number of maximum vertices of transportation polytopes of order $kn\times n$.     

Matching polytopes,toric geometry,and the totally non-negative Grassmannian

In this paper we use toric geometry to investigate the topology of the totally non-negative part of the Grassmannian, denoted (Gr _k,n )_≥0. This is a cell complex whose cells Δ _G can be parameterized in terms of the combinatorics of plane-bipartite graphs G. To each cell Δ _G we associate a certain polytope P(G). The polytopes P(G) are analogous to the well-known Birkhoff polytopes, and we describe their face lattices in terms of matchings and unions of matchings of G. We also demonstrate a close connection between the polytopes P(G) and matroid polytopes. We use the data of P(G) to define an associated toric variety X _G . We use our technology to prove that the cell decomposition of (Gr _k,n )_≥0 is a CW complex, and furthermore, that the Euler characteristic of the closure of each cell of (Gr _k,n )_≥0 is 1. Alexander Postnikov was supported in part by NSF CAREER Award DMS-0504629. David Speyer was supported by a research fellowship from the Clay Mathematics Institute. Lauren Williams was supported in part by the NSF.     

On hyperbolic virtual polytopes and hyperbolic fans

Hyperbolic virtual polytopes arose originally as polytopal versions of counterexamples to the following A.D.Alexandrov’s uniqueness conjecture: Let K ⊂ ℝ³ be a smooth convex body. If for a constant C, at every point of ∂K, we have R ₁ ≤ C ≤ R ₂ then K is a ball. (R ₁ and R ₂ stand for the principal curvature radii of ∂K.) This paper gives a new (in comparison with the previous construction by Y.Martinez-Maure and by G.Panina) series of counterexamples to the conjecture. In particular, a hyperbolic virtual polytope (and therefore, a hyperbolic hérisson) with odd an number of horns is constructed. Moreover, various properties of hyperbolic virtual polytopes and their fans are discussed.     

Coxeter polytopes with a unique pair of non-intersecting facets

We consider compact hyperbolic Coxeter polytopes whose Coxeter diagram contains a unique dotted edge. We prove that such a polytope in d-dimensional hyperbolic space has at most d+3 facets. In view of results by Kaplinskaja [I.M. Kaplinskaya, Discrete groups generated by reflections in the faces of simplicial prisms in Lobachevskian spaces, Math. Notes 15 (1974) 88-91] and the second author [P. Tumarkin, Compact hyperbolic Coxeter n-polytopes with n+3 facets, Electron. J. Combin. 14 (2007), R69, 36 pp.], this implies that compact hyperbolic Coxeter polytopes with a unique pair of non-intersecting facets are completely classified. They do exist only up to dimension 6 and in dimension 8.     

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.     

On the facets of the secondary polytope

The secondary polytope of a point configuration A is a polytope whose face poset is isomorphic to the poset of all regular subdivisions of A. While the vertices of the secondary polytope - corresponding to the triangulations of A - are very well studied, there is not much known about the facets of the secondary polytope.The splits of a polytope, subdivisions with exactly two maximal faces, are the simplest examples of such facets and the first that were systematically investigated. The present paper can be seen as a continuation of these studies and as a starting point of an examination of the subdivisions corresponding to the facets of the secondary polytope in general. As a special case, the notion of k-split is introduced as a possibility to classify polytopes in accordance to the complexity of the facets of their secondary polytopes. An application to matroid subdivisions of hypersimplices and tropical geometry is given.     

Permanental Polytopes of Doubly Stochastic Matrices

A subpolytope Γ of the polytope Ω_n of all n×n nonnegative doubly stochastic matrices is said to be a permanental polytope if the permanent function is constant on Γ. Geometrical properties of permanental polytopes are investigated. No matrix of the form 1⊕A where A is in Ω₂ is contained in any permanental polytope of Ω₃ with positive dimension. There is no 3-dimensional permanental polytope of Ω₃, and there is essentially a unique maximal 2-dimensional permanental polytope of Ω₃ (a square of side $\text{1}\text{3}$). Permanental polytopes of dimension $\text{(n}{}^2\text{?3n+4)}\text{2}$ are exhibited for each n?4.