Search

A combinatorial polytope $P$ is said to be projectively unique if it has a single realization up to projective transformations. Projective uniqueness is a geometrically compelling property but is difficult to verify. In this paper, we merge two approaches to projective uniqueness in the literature. One is primarily geometric and is due to McMullen, who showed that certain natural operations on polytopes preserve projective uniqueness. The other is more algebraic and is due to Gouveia, Macchia, Thomas, and Wiebe. They use certain ideals associated to a polytope to verify a property called graphicality that implies projective uniqueness. In this paper, we show that that McMullen's operations preserve not only projective uniquness but also graphicality. As an application, we show that large families of order polytopes are graphic and thus projectively unique.

We explore upper bounds on the covering radius of non-hollow lattice polytopes. In particular, we conjecture a general upper bound of $d/2$ in dimension $d$, achieved by the "standard terminal simplices" and direct sums of them. We prove this conjecture up to dimension three and show it to be equivalent to the conjecture of González-Merino \& Schymura (2017) that the $d$-th covering minimum of the standard terminal $n$-simplex equals $d/2$, for every $n>d$. We also show that these two conjectures would follow from a discrete analog for lattice simplices of Hadwiger's formula bounding the covering radius of a convex body in terms of the ratio of surface area versus volume. To this end, we introduce a new notion of discrete surface area of non-hollow simplices. We prove our discrete analog in dimension two and we give strong evidence for its validity in arbitrary dimension., 44 pages, 7 figures

Let P be a lattice polytope with the $$h^{*}$$ -vector $$(1, h^*_1, \ldots , h^*_s)$$ . In this note we show that if $$h_s^* \le h_1^*$$ , then the Ehrhart ring $${\mathbb {k}}[P]$$ is generated in degrees at most $$s-1$$ as a $${\mathbb {k}}$$ -algebra. In particular, if $$s=2$$ and $$h_2^* \le h_1^*$$ , then P is IDP. To see this, we show the corresponding statement for semi-standard graded Cohen–Macaulay domains over algebraically closed fields.

A famous and wide-open problem, going back to at least the early 1970s, concerns the classification of chromatic polynomials of graphs. Toward this classification problem, one may ask for necessary inequalities among the coefficients of a chromatic polynomial, and we contribute such inequalities when a chromatic polynomial $$\chi _G(n)=\chi ^*_0\left( {\begin{array}{c}n+d\\ d\end{array}}\right) +\chi ^*_1\left( {\begin{array}{c}n+d-1\\ d\end{array}}\right) +\dots +\chi ^*_d\left( {\begin{array}{c}n\\ d\end{array}}\right) $$ is written in terms of a binomial-coefficient basis. For example, we show that $$\chi ^*_j\le \chi ^*_{d-j}$$ , for $$0\le j\le d/2$$ . Similar results hold for flow and tension polynomials enumerating either modular or integral nowhere-zero flows/tensions of a graph. Our theorems follow from connections among chromatic, flow, tension, and order polynomials, as well as Ehrhart polynomials of lattice polytopes that admit unimodular triangulations. Our results use Ehrhart inequalities due to Athanasiadis and Stapledon and are related to recent work by Hersh–Swartz and Breuer–Dall, where inequalities similar to some of ours were derived using algebraic-combinatorial methods.

The goal of this paper is to design a simplex algorithm for linear programs on lattice polytopes that traces “short” simplex paths from any given vertex to an optimal one. We consider a lattice polytope P contained in $$[0,k]^n$$ and defined via m linear inequalities. Our first contribution is a simplex algorithm that reaches an optimal vertex by tracing a path along the edges of P of length in $$O(n^{4} k\, \hbox {log}\, k).$$ The length of this path is independent from m and it is the best possible up to a polynomial function. In fact, it is only polynomially far from the worst-case diameter, which roughly grows as nk. Motivated by the fact that most known lattice polytopes are defined via $$0,\pm 1$$ constraint matrices, our second contribution is a more sophisticated simplex algorithm which exploits the largest absolute value $$\alpha $$ of the entries in the constraint matrix. We show that the length of the simplex path generated by this algorithm is in $$O(n^2k\, \hbox {log}\, ({nk} \alpha ))$$ . In particular, if $$\alpha $$ is bounded by a polynomial in n, k, then the length of the simplex path is in $$O(n^2k\, \hbox {log}\, (nk))$$ . For both algorithms, if P is “well described”, then the number of arithmetic operations needed to compute the next vertex in the path is polynomial in n, m, and $$\hbox {log}\, k$$ . If k is polynomially bounded in n and m, the algorithm runs in strongly polynomial time.

The Baldoni--Vergne volume and Ehrhart polynomial formulas for flow polytopes are significant in at least two ways. On one hand, these formulas are in terms of Kostant partition functions, connecting flow polytopes to this classical vector partition function fundamental in representation theory. On the other hand the Ehrhart polynomials can be read off from the volume functions of flow polytopes. The latter is remarkable since the leading term of the Ehrhart polynomial of an integer polytope is its volume! Baldoni and Vergne proved these formulas via residues. To reveal the geometry of these formulas, the second author and Morales gave a fully geometric proof for the volume formula and a part generating function proof for the Ehrhart polynomial formula. The goal of the present paper is to provide a fully geometric proof for the Ehrhart polynomial formula of flow polytopes., 11 pages, 3 figures. v2: improvements to exposition

An $$(n+1)$$ -toroid is a quotient of a tessellation of the n-dimensional Euclidean space with a lattice group. Toroids are generalisations of maps on the torus to higher dimensions and also provide examples of abstract polytopes. Equivelar toroids are those that are induced by regular tessellations. In this paper we present a classification of equivelar $$(n+1)$$ -toroids with at most n flag-orbits; in particular, we discuss a classification of 2-orbit toroids of arbitrary dimension.

For fixed k we prove exponential lower bounds on the equilateral number of subspaces of $$\ell _{\infty }^n$$ ℓ ∞ n of codimension k. In particular, we show that subspaces of codimension 2 of $$\ell _{\infty }^{n+2}$$ ℓ ∞ n + 2 and subspaces of codimension 3 of $$\ell _{\infty }^{n+3}$$ ℓ ∞ n + 3 have an equilateral set of cardinality $$n+1$$ n + 1 if $$n\ge 7$$ n ≥ 7 and $$n\ge 12$$ n ≥ 12 respectively. Moreover, the same is true for every normed space of dimension n, whose unit ball is a centrally symmetric polytope with at most $${4n}/{3}-o(n)$$ 4 n / 3 - o ( n ) pairs of facets.

The lattice size of a lattice polytope P was defined and studied by Schicho, and Castryck and Cools. They provided an “onion skins” algorithm for computing the lattice size of a lattice polygon P in $$\mathbb R^2$$ based on passing successively to the convex hull of the interior lattice points of P. We explain the connection of the lattice size to the successive minima of $$K=(P+(-P))^*$$ and to the lattice reduction with respect to the general norm that corresponds to K. It follows that the generalized Gauss algorithm of Kaib and Schnorr (which is faster than the “onion skins” algorithm) computes the lattice size of any convex body in $$\mathbb R^2$$ . We extend the work of Kaib and Schnorr to dimension three, providing a fast algorithm for lattice reduction with respect to the general norm defined by a convex origin-symmetric body $$K\subset \mathbb R^3$$ . We also explain how to recover the successive minima of K and the lattice size of P from the obtained reduced basis and therefore provide a fast algorithm for computing the lattice size of any convex body $$P\subset \mathbb R^3$$ .

Consider a random simplex $[X_1,\ldots,X_n]$ defined as the convex hull of independent identically distributed random points $X_1,\ldots,X_n$ in $\mathbb{R}^{n-1}$ with the following beta density: $$ f_{n-1,\beta} (x) \propto (1-\|x\|^2)^{\beta} 1_{\{\|x\| < 1\}}, \qquad x\in\mathbb{R}^{n-1}, \quad \beta>-1. $$ Let $J_{n,k}(\beta)$ be the expected internal angle of the simplex $[X_1,\ldots,X_n]$ at its face $[X_1,\ldots,X_k]$. Define $\tilde J_{n,k}(\beta)$ analogously for i.i.d. random points distributed according to the beta' density $$ \tilde f_{n-1,\beta} (x) \propto (1+\|x\|^2)^{-\beta}, \qquad x\in\mathbb{R}^{n-1}, \quad \beta > \frac{n-1}{2}. $$ We derive formulae for $J_{n,k}(\beta)$ and $\tilde J_{n,k}(\beta)$ which make it possible to compute these quantities symbolically, in finitely many steps, for any integer or half-integer value of $\beta$. For $J_{n,1}(\pm 1/2)$ we even provide explicit formulae in terms of products of Gamma functions. We give applications of these results to two seemingly unrelated problems of stochastic geometry. (i) We compute the expected $f$-vectors of the typical Poisson-Voronoi cells in dimensions up to $10$. (ii) Consider the random polytope $K_{n,d} := [U_1,\ldots,U_n]$ where $U_1,\ldots,U_n$ are i.i.d. random points sampled uniformly inside some $d$-dimensional convex body $K$ with smooth boundary and unit volume. M. Reitzner proved the existence of the limit of the normalized expected $f$-vector of $K_{n,d}$: $$ \lim_{n\to\infty} n^{-{\frac{d-1}{d+1}}}\mathbb E \mathbf f(K_{n,d}) = \mathbf c_d \cdot \Omega(K), $$ where $\Omega(K)$ is the affine surface area of $K$, and $\mathbf c_d$ is an unknown vector not depending on $K$. We compute $\mathbf c_d$ explicitly in dimensions up to $d=10$ and also solve the analogous problem for random polytopes with vertices distributed uniformly on the sphere., Comment: 30 pages. Minor changes. References updated

We describe an algorithm for computing the min-convex hull of a finite collection of points in the affine building of $$\hbox {SL}_d(K)$$ , for K a field with discrete valuation. These min-convex hulls describe the relations among a finite collection of invertible matrices over K. As a consequence, we bound the dimension of the tropical projective space needed to realize the min-convex hull as a tropical polytope.

Problem 4.19 in Ziegler (Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995)) asserts that every simple 3-dimensional polytope has the property that its dual can be constructed as the convex hull of points chosen from the facets of the original polytope. In this note we state a variant of this conjecture that requires the points to be a subset of the vertices of the original polytope, and provide a family of counterexamples for dimension $$d \ge 3$$ .

All SL(n) contravariant $$L_{p}$$ harmonic valuations on convex polytopes are completely classified without homogeneity assumptions.

A flip is a minimal move between two triangulations of a polytope. The set of triangulations of a polytope was shown by Santos to not always be connected by flips, and it is an interesting problem to find large classes of polytopes for which it is. One such class which has received considerable attention is the product of two simplices. Santos proved that the set of triangulations of a product of two simplices is connected by flips when one of the simplices is a triangle. However, the author showed that it is not connected when one of the simplices is four-dimensional and the other has very large dimension. In this paper we show that it is connected when one of the simplices is a tetrahedron, thereby extending Santos’s result as far as possible.

The problem of deciding if a given triangulation of a sphere can be realized as the boundary sphere of a simplicial, convex polytope is known as the ‘Simplicial Steinitz problem’. It is known by an indirect and non-constructive argument that a vast majority of Bier spheres are non-polytopal. Contrary to that, we demonstrate that the Bier spheres associated to threshold simplicial complexes are all polytopal. Moreover, we show that all Bier spheres are starshaped. We also establish a connection between Bier spheres and Kantorovich–Rubinstein polytopes by showing that the boundary sphere of the KR-polytope associated to a polygonal linkage (weighted cycle) is isomorphic to the Bier sphere of the associated simplicial complex of “short sets”.

A set P = H cup {w} of n+1 points in the plane is called a wheel set if all points but w are extreme. We show that for the purpose of counting crossing-free geometric graphs on P, it suffices to know the so-called frequency vector of P. While there are roughly 2^n distinct order types that correspond to wheel sets, the number of frequency vectors is only about 2^{n/2}. We give simple formulas in terms of the frequency vector for the number of crossing-free spanning cycles, matchings, w-embracing triangles, and many more. Based on these formulas, the corresponding numbers of graphs can be computed efficiently. Also in higher dimensions, wheel sets turn out to be a suitable model to approach the problem of computing the simplicial depth of a point w in a set H, i.e., the number of simplices spanned by H that contain w. While the concept of frequency vectors does not generalize easily, we show how to apply similar methods in higher dimensions. The result is an O(n^{d-1}) time algorithm for computing the simplicial depth of a point w in a set H of n d-dimensional points, improving on the previously best bound of O(n^d log n). Configurations equivalent to wheel sets have already been used by Perles for counting the faces of high-dimensional polytopes with few vertices via the Gale dual. Based on that we can compute the number of facets of the convex hull of n=d+k points in general position in R^d in time O(n^max(omega,k-2)) where omega = 2.373, even though the asymptotic number of facets may be as large as n^k., Leibniz International Proceedings in Informatics (LIPIcs), 77, ISSN:1868-8969, 33rd International Symposium on Computational Geometry (SoCG 2017), ISBN:978-3-95977-038-5

In the classical setting, a convex polytope is called semiregular if its facets are regular and its symmetry group is transitive on vertices. This paper continues our study of alternating abstract semiregular polytopes $$\mathcal {S}$$ . These structures have two kinds of abstract regular facets $$\mathcal {P}$$ and $$\mathcal {Q}$$ , still with combinatorial automorphism group transitive on vertices. Furthermore, for some interlacing number $$k\geqslant 1$$ , k copies each of $$\mathcal {P}$$ and $$\mathcal {Q}$$ can be assembled in alternating fashion around each face of co-rank 2 in $$\mathcal {S}$$ . Here we focus on constructions involving interesting pairs of polytopes $$\mathcal {P}$$ and $$\mathcal {Q}$$ . In some cases, $$\mathcal {S}$$ can be constructed for general values of k. In other remarkable instances, interlacing with certain finite interlacing numbers proves impossible.

We show that for all integers m⩾ 2 ,and all integers k⩾ 2 ,the orthogonal groups O±(2m,F2k) act on abstract regular polytopes of rank 2m, and the symplectic groups Sp(2m,F2k) act on abstract regular polytopes of rank 2 m+ 1., SCOPUS: ar.j, info:eu-repo/semantics/published

We study an alternating sign matrix analogue of the Chan–Robbins–Yuen polytope, which we call the ASM-CRY polytope. We show that this polytope has Catalan many vertices and its volume is equal to the number of standard Young tableaus of staircase shape; we also determine its Ehrhart polynomial. We achieve the previous by proving that the members of a family of faces of the alternating sign matrix polytope which includes ASM-CRY are both order and flow polytopes. Inspired by the above results, we relate three established triangulations of order and flow polytopes, namely Stanley’s triangulation of order polytopes, the Postnikov–Stanley triangulation of flow polytopes and the Danilov–Karzanov–Koshevoy triangulation of flow polytopes. We show that when a graph G is a planar graph, in which case the flow polytope $${{\mathcal {F}}}_G$$ is also an order polytope, Stanley’s triangulation of this order polytope is one of the Danilov–Karzanov–Koshevoy triangulations of $${{\mathcal {F}}}_G$$ . Moreover, for a general graph G we show that the set of Danilov–Karzanov–Koshevoy triangulations of $${{\mathcal {F}}}_G$$ equals the set of framed Postnikov–Stanley triangulations of $${{\mathcal {F}}}_G$$ . We also describe explicit bijections between the combinatorial objects labeling the simplices in the above triangulations.

A somewhat fundamental sequence of antiprisms is defined, the d-th antiprism having dimension d, each being a base of the next. The f-vectors of these polytopes are determined. In particular, it is shown that the number of faces of the d-th antiprism is the number of partitions of $$2^{d+1}$$ into powers of 2. In order to better understand the structure of the face lattices of these polytopes and their interrelationship, it is convenient also to introduce a countably infinite lattice, the elements of which correspond to the partitions of powers of 2 into powers of 2. This lattice has the property that it is isomorphic to its lattice of intervals, and it is the smallest such lattice.

The normalized volume of the Chan–Robbins–Yuen polytope ( $$CRY_n$$ ) is the product of consecutive Catalan numbers. The polytope $$CRY_n$$ has captivated combinatorial audiences for over a decade, as there is no combinatorial proof for its volume formula. In their quest to understand $$CRY_n$$ better, the third author and Morales introduced two natural generalizations of it and conjectured that their volumes are certain powers of 2 multiplied by a product of consecutive Catalan numbers. Zeilberger proved one of these conjectures. In this paper we present proofs of both conjectures.

While much research has been done on the Ehrhart functions of integral and rational polytopes, little is known in the irrational case. In our main theorem, we determine exactly when the Ehrhart function of a right triangle with legs on the axes and slant edge with irrational slope is a polynomial. We also investigate several other situations where the period of the Ehrhart function of a polytope is less than the denominator of that polytope. For example, we give examples of irrational polytopes with polynomial Ehrhart function in any dimension, and we find triangles with periods dividing any even-index k-Fibonacci number, but with larger denominators.

It is known that polytopes with at most two nonsimple vertices are reconstructible from their graphs, and that $d$-polytopes with at most $d-2$ nonsimple vertices are reconstructible from their 2-skeletons. Here we close the gap between 2 and $d-2$, showing that certain polytopes with more than two nonsimple vertices are reconstructible from their graphs. In particular, we prove that reconstructibility from graphs also holds for $d$-polytopes with $d+k$ vertices and at most $d-k+3$ nonsimple vertices, provided $k\ge 5$. For $k\le4$, the same conclusion holds under a slightly stronger assumption. Another measure of deviation from simplicity is the {\it excess degree} of a polytope, defined as $\xi(P):=2f_1-df_0$, where $f_k$ denotes the number of $k$-dimensional faces of the polytope. Simple polytopes are those with excess zero. We prove that polytopes with excess at most $d-1$ are reconstructible from their graphs, and this is best possible. An interesting intermediate result is that $d$-polytopes with less than $2d$ vertices, and at most $d-1$ nonsimple vertices, are necessarily pyramids., Comment: 17 pages

It is natural to ask whether the center of mass of a convex body $K\subset \mathbb{R}^n$ lies in its John ellipsoid $B_K$, i.e., in the maximal volume ellipsoid contained in $K$. This question is relevant to the efficiency of many algorithms for convex bodies. In this paper, we obtain an unexpected negative result. There exists a convex body $K\subset \mathbb{R}^n$ such that its center of mass does not lie in the John ellipsoid $B_K$ inflated $(1-C\sqrt{\frac{\log(n)} {n}})n$ times about the center of $B_K$. Moreover, there exists a polytope $P \subset \mathbb{R}^n$ with $O(n^2)$ facets whose center of mass is not contained in the John ellipsoid $B_P$ inflated $O(\frac{n}{\log(n)})$ times about the center of $B_P$., Comment: In the original version, we've shown that there exists a convex body $K\subset \mathbb{R}^n$ such that its center of mass does not lie in the John ellipsoid $B_K$ inflated $cn$ times about the center of $B_K$ for some universal constant $c>0$. This time we replaced the constant $cn$ by $(1-C\sqrt{\frac{\log(n)} {n}})n$ for some universal constant $C>0$, which is sharp since it cannot exceed $n$. arXiv admin note: text overlap with arXiv:1703.02173

Shape-constrained density estimation is an important topic in mathematical statistics. We focus on densities on $\mathbb{R}^d$ that are log-concave, and we study geometric properties of the maximum likelihood estimator (MLE) for weighted samples. Cule, Samworth, and Stewart showed that the logarithm of the optimal log-concave density is piecewise linear and supported on a regular subdivision of the samples. This defines a map from the space of weights to the set of regular subdivisions of the samples, i.e. the face poset of their secondary polytope. We prove that this map is surjective. In fact, every regular subdivision arises in the MLE for some set of weights with positive probability, but coarser subdivisions appear to be more likely to arise than finer ones. To quantify these results, we introduce a continuous version of the secondary polytope, whose dual we name the Samworth body. This article establishes a new link between geometric combinatorics and nonparametric statistics, and it suggests numerous open problems., Comment: 22 pages, 3 figures

In this paper we present an explicit combinatorial description of a special class of facets of the secondary polytopes of hypersimplices. These facets correspond to polytopal subdivisions called multi-splits. We show a relation between the cells in a multi-split of the hypersimplex and nested matroids. Moreover, we get a description of all multi-splits of a product of simplices. Additionally, we present a computational result to derive explicit lower bounds on the number of facets of secondary polytopes of hypersimplices., 21 pages, 4 figures, 2 tables

We show that the Simion type B associahedron is combinatorially equivalent to a pulling triangulation of the type A root polytope known as the Legendre polytope. Furthermore, we show that every pulling triangulation of the boundary of the Legendre polytope yields a flag complex. Our triangulation refines a decomposition of the boundary of the Legendre polytope given by Cho. Finally, we extend Cho’s cyclic group action to the triangulation in such a way that it corresponds to rotating centrally symmetric triangulations of a regular $$(2n+2)$$ -gon.