Search

We show that for every simplicial polytope an inscribed simplicial polytope exists that has the same dimension, number of vertices, number of edges, and number of 2-faces. This proves that the g-theorem for simplicial polytopes also holds for the class of inscribed simplicial polytopes (up to dimension 7). The proof includes an incremental construction scheme for Delaunay triangulations. [ABSTRACT FROM AUTHOR]

We show that the shallow packing lemma follows from a simple modification of the standard proof, due to Haussler and simplified by Chazelle, of the packing lemma. [ABSTRACT FROM AUTHOR]

We study the expected value of support functions of random polytopes in a certain direction, where the random polytope is given by independent random vectors uniformly distributed in an isotropic convex body. All results are obtained using probabilistic estimates in terms of Orlicz norms that were not used in this connection before. [ABSTRACT FROM AUTHOR]

We present explicit constructions of centrally symmetric $$2$$-neighborly $$d$$-dimensional polytopes with about $$3^{d/2}\approx (1.73)^d$$ vertices and of centrally symmetric $$k$$-neighborly $$d$$-polytopes with about $$2^{{3d}/{20k^2 2^k}}$$ vertices. Using this result, we construct for a fixed $$k\ge 2$$ and arbitrarily large $$d$$ and $$N$$, a centrally symmetric $$d$$-polytope with $$N$$ vertices that has at least $$\left( 1-k^2\cdot (\gamma _k)^d\right) \genfrac(){0.0pt}{}{N}{k}$$ faces of dimension $$k-1$$, where $$\gamma _2=1/\sqrt{3}\approx 0.58$$ and $$\gamma _k = 2^{-3/{20k^2 2^k}}$$ for $$k\ge 3$$. Another application is a construction of a set of $$3^{\lfloor d/2 -1\rfloor }-1$$ points in $$\mathbb R ^d$$ every two of which are strictly antipodal as well as a construction of an $$n$$-point set (for an arbitrarily large $$n$$) in $$\mathbb R ^d$$ with many pairs of strictly antipodal points. The two latter results significantly improve the previous bounds by Talata, and Makai and Martini, respectively. [ABSTRACT FROM AUTHOR]

We study the structure of the space of diametrically complete sets in a finite dimensional normed space. In contrast to the Euclidean case, this space is in general not convex. We show that its starshapedness is equivalent to the completeness of the parallel bodies of complete sets, a property studied in Moreno and Schneider (Isr. J. Math. , doi:), which is generically not satisfied. The space in question is, however, always contractible. Our main result states that in the case of a polyhedral norm, the space of translation classes of diametrically complete sets of given diameter is a finite polytopal complex. The proof makes use of a diagram technique, due to P. McMullen, for the representation of translation classes of polytopes with given normal vectors. The paper concludes with a study of the extreme diametrically complete sets. [ABSTRACT FROM AUTHOR]

Quite recently, an Orlicz Minkowski problem has been posed and the existence part of this problem for even measures has been presented. In this paper, the existence part of the Orlicz Minkowski problem for polytopes is demonstrated. Furthermore, we obtain a solution of the Orlicz Minkowski problem for general (not necessarily even) measures. [ABSTRACT FROM AUTHOR]

We show that the cyclic lamplighter group C2 ≀ C n embeds into Hilbert space with distortion $\mathrm{O}(\sqrt{\log n})$ . This matches the lower bound proved by Lee et al. (Geom. Funct. Anal., ), answering a question posed in that paper. Thus, the Euclidean distortion of C2 ≀ C n is $\varTheta(\sqrt{\log n})$ . Our embedding is constructed explicitly in terms of the irreducible representations of the group. Since the optimal Euclidean embedding of a finite group can always be chosen to be equivariant, as shown by Aharoni et al. (Isr. J. Math. 52(3):251–265, ) and by Gromov (see de Cornulier et. al. in Geom. Funct. Anal., ), such representation-theoretic considerations suggest a general tool for obtaining upper and lower bounds on Euclidean embeddings of finite groups. [ABSTRACT FROM AUTHOR]

A split of a polytope is a (necessarily regular) subdivision with exactly two maximal cells. A polytope is totally splittable if each triangulation (without additional vertices) is a common refinement of splits. This paper establishes a complete classification of the totally splittable polytopes. [ABSTRACT FROM AUTHOR]

We investigate polyhedral 2 k-manifolds as subcomplexes of the boundary complex of a regular polytope. We call such a subcomplex k -Hamiltonian if it contains the full k-skeleton of the polytope. Since the case of the cube is well known and since the case of a simplex was also previously studied (these are so-called super-neighborly triangulations), we focus on the case of the cross polytope and the sporadic regular 4-polytopes. By our results the existence of 1-Hamiltonian surfaces is now decided for all regular polytopes. Furthermore we investigate 2-Hamiltonian 4-manifolds in the d-dimensional cross polytope. These are the “regular cases” satisfying equality in Sparla’s inequality. In particular, we present a new example with 16 vertices which is highly symmetric with an automorphism group of order 128. Topologically it is homeomorphic to a connected sum of seven copies of S2× S2. By this example all regular cases of n vertices with n<20 or, equivalently, all cases of regular d-polytopes with d≤9 are now decided. [ABSTRACT FROM AUTHOR]

We investigate properties of Ehrhart polynomials for matroid polytopes, independence matroid polytopes, and polymatroids. In the first half of the paper we prove that, for fixed rank, Ehrhart polynomials of matroid polytopes and polymatroids are computable in polynomial time. The proof relies on the geometry of these polytopes as well as a new refined analysis of the evaluation of Todd polynomials. In the second half we discuss two conjectures about the h*-vector and the coefficients of Ehrhart polynomials of matroid polytopes; we provide theoretical and computational evidence for their validity. [ABSTRACT FROM AUTHOR]

In previous papers, all the four-dimensional (finite) regular polytopes have been classified, as well as the regular apeirotopes of full rank (that is, of rank 5). Of the two problems in $\mathbb{E}^{4}$ thus left open (namely, regular apeirotopes of ranks 3 and 4), this paper describes the regular apeirotopes of rank 4. The methods employed here are somewhat different from those in earlier work; while knowledge of the possible dimension vectors (dim R0,...,dim R3) of the mirrors R0,..., R3 of the generating reflexions of the symmetry groups plays a rôle, the crystallographic restriction leads to a considerable emphasis being placed on the vertex-figures. [ABSTRACT FROM AUTHOR]

In 1989, Kalai stated three conjectures A, B, C of increasing strength concerning face numbers of centrally symmetric convex polytopes. The weakest conjecture, A, became known as the “3 d -conjecture.” It is well known that the three conjectures hold in dimensions d≤3. We show that in dimension 4 only conjectures A and B are valid, while conjecture C fails. Furthermore, we show that both conjectures B and C fail in all dimensions d≥5. [ABSTRACT FROM AUTHOR]

In (Gluskin, Litvak in Geom. Dedicate 90:45–48, []) it was shown that a polytope with few vertices is far from being symmetric in the Banach–Mazur distance. More precisely, it was shown that Banach–Mazur distance between such a polytope and any symmetric convex body is large. In this note we introduce a new, averaging-type parameter to measure the asymmetry of polytopes. It turns out that, surprisingly, this new parameter is still very large, in fact it satisfies the same lower bound as the Banach–Mazur distance. In a sense it shows the following phenomenon: if a convex polytope with small number of vertices is as close to a symmetric body as it can be, then most of its vertices are as bad as the worst one. We apply our results to provide a lower estimate on the vertex index of a symmetric convex body, which was recently introduced in (Bezdek, Litvak in Adv. Math. 215:626–641, []). Furthermore, we give the affirmative answer to a conjecture by Bezdek (Period. Math. Hung. 53:59–69, []) on the quantitative illumination problem. [ABSTRACT FROM AUTHOR]

Abstract  For polytopes P 1,P 2⊂ℝ d , we consider the intersection P 1∩P 2, the convex hull of the union CH(P 1∪P 2), and the Minkowski sum P 1+P 2. For the Minkowski sum, we prove that enumerating the facets of P 1+P 2 is NP-hard if P 1 and P 2 are specified by facets, or if P 1 is specified by vertices and P 2 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. [ABSTRACT FROM AUTHOR]

Abstract   We express the generating function for lattice points in a rational polyhedral cone with a simplicial subdivision in terms of multivariate analogues of the h-polynomials of the subdivision and “local contributions” of the links of its nonunimodular faces. We also compute new examples of nonunimodal h *-vectors of reflexive polytopes. [ABSTRACT FROM AUTHOR]

Abstract   We define a centrally symmetric analogue of the cyclic polytope and study its facial structure. We conjecture that our polytopes provide asymptotically the largest number of faces in all dimensions among all centrally symmetric polytopes with n vertices of a given even dimension d=2k when d is fixed and n grows. For a fixed even dimension d=2k and an integer 1≤jk we prove that the maximum possible number of j-dimensional faces of a centrally symmetric d-dimensional polytope with n vertices is at least for some c j (d)>0 and at most as n grows. We show that c 1(d)≥1−(d−1)−1 and conjecture that the bound is best possible. [ABSTRACT FROM AUTHOR]

Abstract   We construct CW spheres from the lattices that arise as the closed sets of a convex closure, the meet-distributive lattices. These spheres are nearly polytopal, in the sense that their barycentric subdivisions are simplicial polytopes. The complete information on the numbers of faces and chains of faces in these spheres can be obtained from the defining lattices in a manner analogous to the relation between arrangements of hyperplanes and their underlying geometric intersection lattices. [ABSTRACT FROM AUTHOR]

Abstract   For convex bodies K with boundary in ℝ d , we explore random polytopes with vertices chosen along the boundary of K. In particular, we determine asymptotic properties of the volume of these random polytopes. We provide results concerning the variance and higher moments of this functional, as well as an analogous central limit theorem. [ABSTRACT FROM AUTHOR]

Abstract  A known characterization of the decomposability of polytopes is reformulated in a way which may be more computationally convenient, and a more transparent proof is given. New sufficient conditions for indecomposability are then deduced, and illustrated with some examples. [ABSTRACT FROM AUTHOR]

Abstract   We prove that for d≥3, the 1-skeleton of any (d−1)-dimensional doubly Cohen–Macaulay (abbreviated 2-CM) complex is generically d-rigid. This implies that Barnette’s lower bound inequalities for boundary complexes of simplicial polytopes (Barnette, D. Isr. J. Math. 10:121–125, 1971; Barnette, D. Pac. J. Math. 46:349–354, 1973) hold for every 2-CM complex of dimension ≥2 (see Kalai, G. Invent. Math. 88:125–151, 1987). Moreover, the initial part (g 0,g 1,g 2) of the g-vector of a 2-CM complex (of dimension ≥3) is an M-sequence. It was conjectured by Björner and Swartz (J. Comb. Theory Ser. A 113:1305–1320, 2006) that the entire g-vector of a 2-CM complex is an M-sequence. [ABSTRACT FROM AUTHOR]

Abstract  The conjecture of Kalai, Kleinschmidt, and Lee on the number of empty simplices of a simplicial polytope is established by relating it to the first graded Betti numbers of the polytope and applying a result of Migliore and the author. This approach allows us to derive explicit optimal bounds on the number of empty simplices of any given dimension. As a key result, we prove optimal bounds for the graded Betti numbers of any standard graded K-algebra in terms of its Hilbert function. [ABSTRACT FROM AUTHOR]

Abstract  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. [ABSTRACT FROM AUTHOR]

Abstract  We determine lattice polytopes of smallest volume with a given number of interior lattice points. We show that the Ehrhart polynomials of those with one interior lattice point have largest roots with norm of order n2, where n is the dimension. This improves on the previously best known bound n and complements a recent result of Braun where it is shown that the norm of a root of a Ehrhart polynomial is at most of order n2. For the class of 0-symmetric lattice polytopes we present a conjecture on the smallest volume for a given number of interior lattice points and prove the conjecture for crosspolytopes. We further give a characterisation of the roots of Ehrhart polyomials in the three-dimensional case and we classify for n ≤ 4 all lattice polytopes whose roots of their Ehrhart polynomials have all real part -1/2. These polytopes belong to the class of reflexive polytopes. [ABSTRACT FROM AUTHOR]

Abstract  We consider polytopes in that are generated by N vectors in whose coordinates are independent subgaussian random variables. (A particular case of such polytopes are symmetric random polytopes generated by N independent vertices of the unit cube.) We show that for a random pair of such polytopes the Banach-Mazur distance between them is essentially of a maximal order n. This result is an analogue of the well-known Gluskin's result for spherical vectors. We also study the norms of projections on such polytopes and prove an analogue of Gluskin's and Szarek's results on basis constants. The proofs are based on a version of "small ball" estimates for linear images of random subgaussian vectors. [ABSTRACT FROM AUTHOR]

Abstract  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. [ABSTRACT FROM AUTHOR]

Abstract??In this paper we prove four new (infinite) lists of quadratic inequalities, and four cubic inequalities, for the flag f-vectors of 4-polytopes. These extend and supplement the only four currently known non-linear inequalities, which were proved by Bayer in 1987. The new lists of inequalities for flag f-vectors yield new lists of inequalities for f-vectors of 4-polytopes. Using the latter, we managed to improve an estimate discovered by Hoppner and Ziegler concerning upper bounds of f1in terms of f0and f3. [ABSTRACT FROM AUTHOR]

Abstract??Using new number-theoretic bounds on the denominators of unit fractions summing up to one, we show that in any dimension d ? 4 there is only one d-dimensional reflexive simplex having maximal volume. Moreover, only these reflexive simplices can admit an edge that has the maximal number of lattice points possible for an edge of a reflexive simplex. In general, these simplices are also expected to contain the largest number of lattice points even among all lattice polytopes with only one interior lattice point. Translated in algebro-geometric language, our main theorem yields a sharp upper bound on the anticanonical degree of d-dimensional Q-factorial Gorenstein toric Fano varieties with Picard number one, e.g., of weighted projective spaces with Gorenstein singularities. [ABSTRACT FROM AUTHOR]

We formulate and prove a rearrangement type inequality and use it to give a description of the face lattice of a certain polytope that is naturally associated to the alternating group An. [ABSTRACT FROM AUTHOR]

Let P be a (non-necessarily convex) embedded polyhedron in R 3, with its vertices on the boundary of an ellipsoid. Suppose that the interior of $P$ can be decomposed into convex polytopes without adding any vertex. Then P is infinitesimally rigid. More generally, let P be a polyhedron bounding a domain which is the union of polytopes C 1, . . ., C n with disjoint interiors, whose vertices are the vertices of P. Suppose that there exists an ellipsoid which contains no vertex of P but intersects all the edges of the C i. Then P is infinitesimally rigid. The proof is based on some geometric properties of hyperideal hyperbolic polyhedra. [ABSTRACT FROM AUTHOR]

Let L be a set of n lines in space. A joint of L is a point in R 3 where at least three non-coplanar lines meet. We show that the number of joints of L is O(n 112/69 log 6/23n)=O(n 1.6232), improving the previous bound O(n 1.643) of Sharir. [ABSTRACT FROM AUTHOR]

For any set A of n points in R 2, we define a (3n - 3)-dimensional simple polyhedron whose face poset is isomorphic to the poset of ”non-crossing marked graphs” with vertex set A, where a marked graph is defined as a geometric graph together with a subset of its vertices. The poset of non-crossing graphs on A appears as the complement of the star of a face in that polyhedron. The polyhedron has a unique maximal bounded face, of dimension 2n i + n - 3 where n i is the number of points of A in the interior of conv (A). The vertices of this polytope are all the pseudo-triangulations of A, and the edges are flips of two types: the traditional diagonal flips (in pseudo-triangulations) and the removal or insertion of a single edge. As a by-product of our construction we prove that all pseudo-triangulations are infinitesimally rigid graphs. [ABSTRACT FROM AUTHOR]

For the first time complete lists of two pairs of inner and outer radii classes of the three types of regular polytopes which exist in all dimensions are presented. A new approach using isotropic polytopes provides better understanding of the underlying geometry and helps to unify the results. [ABSTRACT FROM AUTHOR]

This paper is a study of the polyhedral geometry of Gelfand–Tsetlin polytopes arising in the representation theory of ${\frak gl}_n \Bbb C$ and algebraic combinatorics. We present a combinatorial characterization of the vertices and a method to calculate the dimension of the lowest-dimensional face containing a given Gelfand–Tsetlin pattern. As an application, we disprove a conjecture of Berenstein and Kirillov about the integrality of all vertices of the Gelfand–Tsetlin polytopes. We can construct for each $n\geq5$ a counterexample, with arbitrarily increasing denominators as $n$ grows, of a nonintegral vertex. This is the first infinite family of nonintegral polyhedra for which the Ehrhart counting function is still a polynomial. We also derive a bound on the denominators for the nonintegral vertices when $n$ is fixed. [ABSTRACT FROM AUTHOR]

With a slight modification of the original definition by Billera and Sturmfels, it is shown that the theory of fibre polytopes extends to one of mixed fibre polytopes. Indeed, there is a natural surjective homomorphism from the space of tensor weights on polytopes in a euclidean space V to the corresponding space of such weights on fibre polytopes in a subspace of V. Moreover, these homomorphisms compose in the correct way; this is in contrast to the original situation of the fibre polytope construction. [ABSTRACT FROM AUTHOR]

We describe and analyze a new construction that produces new Eulerian lattices from old ones. It specializes to a construction that produces new strongly regular cellular spheres (whose face lattices are Eulerian). The construction does not always specialize to convex polytopes; however, in a number of cases where we can realize it, it produces interesting classes of polytopes. Thus we produce an infinite family of rational 2-simplicial 2-simple 4-polytopes, as requested by Eppstein et al. We also construct for each d = 3 an infinite family of (d – 2)-simplicial 2-simple d-polytopes, thus solving a problem of Grünbaum. [ABSTRACT FROM AUTHOR]

The dimension of a faithful realization of a finite abstract regular polytope in some euclidean space is no smaller than its rank. Similarly, that of a discrete faithful realization of a regular apeirotope is at least one fewer than the rank. Realizations which attain the minimum are said to be of full rank. The regular polytopes and apeirotopes of full rank in two and three dimensions were classified in an earlier paper. In this paper these polytopes and apeirotopes are classified in all dimensions. Moreover, it is also shown that there are no chiral polytopes of full rank. [ABSTRACT FROM AUTHOR]

We derive improved bounds on the complexity, i.e., the total number of faces of all dimensions, of many cells in arrangements of hyperplanes in higher dimensions, and use these bounds to obtain a very simple proof of an earlier bound, due to Aronov, Matousek, and Sharir, on the sum of squares of cell complexities in such an arrangement. [ABSTRACT FROM AUTHOR]

Let $P$ and $Q$ be polytopes, the first of ?low? dimension and the second of ?high? dimension. We show how to triangulate the product $P \times Q$ efficiently (i.e., with few simplices) starting with a given triangulation of $Q$. Our method has a computational part, where we need to compute an efficient triangulation of $P \times \Delta^m$, for a (small) natural number $m$ of our choice. $\Delta^m$ denotes the $m$-simplex. Our procedure can be applied to obtain (asymptotically) efficient triangulations of the cube $I^n$: We decompose $I^n = I^k \times I^{n-k}$, for a small $k$. Then we recursively assume we have obtained an efficient triangulation of the second factor and use our method to triangulate the product. The outcome is that using $k=3$ and $m=2$, we can triangulate $I^n$ with $O(0.816^{n} n!)$ simplices, instead of the $O(0.840^{n} n!)$ achievable before. [ABSTRACT FROM AUTHOR]

Generalizing a result of Stanley on centrally symmetric polytopes, Adin has derived tight lower bounds for the face numbers of a rational simplical polytope equipped with a fixed-point-free linear action of a cyclic group G of prime power order. The main goal of this paper is to extend these results further by replacing Adin?s fixed-point-free condition with the assumption that the action of G is proper. As corollaries, we obtain a generalization of Adin?s equivariant lower bound theorem and of a condition by Stanley implying combinatorial isomorphism with a minimal polytope. Finally, we prove sufficiency of an equivariant version of the McMullen and Walkup generalized lower bound conjecture. [ABSTRACT FROM AUTHOR]

A small family of regular polytopes of nearly full rank was omitted from the earlier paper with this title. This omission is rectified here. [ABSTRACT FROM AUTHOR]