Gaps in the numbers of vertices of cubical polytopes,I

A cubical polytope is a convex polytope of which very facet is a combinatorial cube. We ask for the numbers which occur as vertex numbers ofd-dimensional cubical polytopes, and we show, as a first step, that every cubicald-polytope for evend≥4 has an even number of vertices.     

The lower and upper bound problems for cubical polytopes

We construct a family of cubical polytypes which shows that the upper bound on the number of facets of a cubical polytope (given a fixed number of vertices) is higher than previously suspected. We also formulate a lower bound conjecture for cubical polytopes.This paper was researched and written while the author was a graduate student at MIT. The author was partially supported by an NSF Graduate Fellowship.     

Lower Bounds for Cubical Pseudomanifolds

It is verified that the number of vertices in a d-dimensional cubical pseudomanifold is at least 2 ^d+1. Using Adin’s cubical h-vector, the generalized lower bound conjecture is established for all cubical 4-spheres, as well as for some special classes of cubical spheres in higher dimensions.     

A family of neighborly polytopes

Ad-polytopeP is said to be neighborly provided each [d/2] vertices determine a face ofP. We construct a family ofd-polytopes that are dual to neighborly polytopes by means of facet splitting. We use this family to find a lower bound on the number of combinatorial types of neighborly polytopes. We also show that all members of this family satisfy the famous Hirsch conjecture. Research supported by NSF Grant # MCS-07466.     

A Centrally Symmetric Version of the Cyclic Polytope

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≤j<k 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 ₁(d)≥1−(d−1)⁻¹ and conjecture that the bound is best possible. Research of A. Barvinok partially supported by NSF grant DMS 0400617. Research of I. Novik partially supported by Alfred P. Sloan Research Fellowship and NSF grant DMS-0500748.     

Construction and Analysis of Projected Deformed Products

We introduce a deformed product construction for simple polytopes in terms of lower-triangular block matrix representations. We further show how Gale duality can be employed for the construction and the analysis of deformed products such that specified faces (e.g., all the k-faces) are “strictly preserved” under projection. Thus, starting from an arbitrary neighborly simplicial (d?2)-polytope Q on n?1 vertices, we construct a deformed n-cube, whose projection to the last d coordinates yields a neighborly cubical d -polytope. As an extension of the cubical case, we construct matrix representations of deformed products of (even) polygons (DPPs) which have a projection to d-space that retains the complete $(\lfloor\tfrac{d}{2}\rfloor-1)We introduce a deformed product construction for simple polytopes in terms of lower-triangular block matrix representations. We further show how Gale duality can be employed for the construction and the analysis of deformed products such that specified faces (e.g., all the k-faces) are “strictly preserved” under projection. Thus, starting from an arbitrary neighborly simplicial (d−2)-polytope Q on n−1 vertices, we construct a deformed n-cube, whose projection to the last d coordinates yields a neighborly cubical d -polytope. As an extension of the cubical case, we construct matrix representations of deformed products of (even) polygons (DPPs) which have a projection to d-space that retains the complete (?\tfracd2?-1)(\lfloor\tfrac{d}{2}\rfloor-1) -skeleton.     

Neighborly Cubical Polytopes

Neighborly cubical polytopes exist: for any n≥ d≥ 2r+2 , there is a cubical convex d -polytope C _d ⁿ whose r -skeleton is combinatorially equivalent to that of the n -dimensional cube. This solves a problem of Babson, Billera, and Chan. Kalai conjectured that the boundary of a neighborly cubical polytope C _d ⁿ maximizes the f -vector among all cubical (d-1) -spheres with 2 ⁿ vertices. While we show that this is true for polytopal spheres if n≤ d+1 , we also give a counterexample for d=4 and n=6 . Further, the existence of neighborly cubical polytopes shows that the graph of the n -dimensional cube, where n\ge5 , is ``dimensionally ambiguous' in the sense of Grünbaum. We also show that the graph of the 5 -cube is ``strongly 4 -ambiguous.' In the special case d=4 , neighborly cubical polytopes have f ₃ =(f ₀ /4) log ₂ (f ₀ /4) vertices, so the facet—vertex ratio f ₃ /f ₀ is not bounded; this solves a problem of Kalai, Perles, and Stanley studied by Jockusch. Received December 30, 1998. Online publication May 15, 2000.     

On the Stanley ring of cubical complex

We investigate the properties of the Stanley ring of a cubical complex, a cubical analogue of the Stanley-Reisner ring of a simplicial complex. We compute its Hilbert series in terms of thef-vector, and prove that by taking the initial ideal of the defining relations, with respect to the reverse lexicographic order, we obtain the defining relations of the Stanley-Reisner ring of the triangulation via “pulling the vertices” of the cubical complex. Applying an old idea of Hochster we see that this ring is Cohen-Macaulay when the complex is shellable, and we show that its defining ideal is generated by quadrics when the complex is also a subcomplex of the boundary complex of a convex cubical polytope. We present a cubical analogue of balanced Cohen-Macaulay simplicial complexes: the class of edge-orientable shellable cubical complexes. Using Stanley's results about balanced Cohen-Macaulay simplicial complexes and the degree two homogeneous generating system of the defining ideal, we obtain an infinite set of examples for a conjecture of Eisenbud, Green, and Harris. This conjecture says that theh-vector of a polynomial ring inn variables modulo an ideal which has ann-element homogeneous system of parameters of degree two, is thef-vector of a simplicial complex.     

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.     

Graph theorems for manifolds

Two basic theorems about the graphs of convex polytopes are that the graph of ad-polytope isd-connected and that it contains a refinement of the complete graph ond+1 vertices. We obtain generalizations of these theorems, and others, for manifolds. We also supply some details for a proof of the lower bound inequality for manifolds. Research supported by NSF Grants GP 8470 and GP 19221.     

Polytopes in Arrangements

Consider an arrangement of n hyperplanes in \real ^d . Families of convex polytopes whose boundaries are contained in the union of the hyperplanes are the subject of this paper. We aim to bound their maximum combinatorial complexity. Exact asymptotic bounds were known for the case where the polytopes are cells of the arrangement. Situations where the polytopes are pairwise openly disjoint have also been considered in the past. However, no nontrivial bound was known for the general case where the polytopes may have overlapping interiors, for d>2 . We analyze families of polytopes that do not share vertices. In \real ³ we show an O(k ^1/3 n ² ) bound on the number of faces of k such polytopes. We also discuss worst-case lower bounds and higher-dimensional versions of the problem. Among other results, we show that the maximum number of facets of k pairwise vertex-disjoint polytopes in \real ^d is Ω(k ^1/2 n ^d/2 ) which is a factor of away from the best known upper bound in the range n ^d-2 ≤ k ≤ n ^d . The case where 1≤ k ≤ n ^d-2 is completely resolved as a known Θ(kn) bound for cells applies here. Received September 20, 1999, and in revised form March 10, 2000. Online publication September 22, 2000.     

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.     

Combinatorial Groupoids,Cubical Complexes,and the Lovász Conjecture

This paper lays the foundation for a theory of combinatorial groupoids that allows us to use concepts like “holonomy”, “parallel transport”, “bundles”, “combinatorial curvature”, etc. in the context of simplicial (polyhedral) complexes, posets, graphs, polytopes and other combinatorial objects. We introduce a new, holonomy-type invariant for cubical complexes, leading to a combinatorial “Theorema Egregium” for cubical complexes that are non-embeddable into cubical lattices. Parallel transport of Hom-complexes and maps is used as a tool to extend Babson–Kozlov–Lovász graph coloring results to more general statements about nondegenerate maps (colorings) of simplicial complexes and graphs. The author was supported by grants 144014 and 144026 of the Serbian Ministry of Science and Technology.     

On Overlays and Minimization Diagrams

The overlay of 2≤m≤d minimization diagrams of n surfaces in ℝ ^d is isomorphic to a substructure of a suitably constructed minimization diagram of mn surfaces in ℝ ^d+m−1. This elementary observation leads to a new bound on the complexity of the overlay of minimization diagrams of collections of d-variate semi-algebraic surfaces, a tight bound on the complexity of the overlay of minimization diagrams of collections of hyperplanes, and faster algorithms for constructing such overlays. Further algorithmic implications are discussed. Work by V. Koltun was supported by NSF CAREER award CCF-0641402. Work by M. Sharir was supported by NSF Grants CCR-00-98246 and CCF-05-14079, by a grant from the Israeli Academy of Sciences for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.     

Cyclotomic and simplicial matroids

We show that two naturally occurring matroids representable over ℚ are equal: thecyclotomic matroid μ_n represented by then ^th roots of unity 1, ζ, ζ², …, ζ^n-1 inside the cyclotomic extension ℚ(ζ), and a direct sum of copies of a certain simplicial matroid, considered originally by Bolker in the context of transportation polytopes. A result of Adin leads to an upper bound for the number of ℚ-bases for ℚ(ζ) among then ^th roots of unity, which is tight if and only ifn has at most two odd prime factors. In addition, we study the Tutte polynomial of μ_n in the case thatn has two prime factors. First author supported by NSF Postdoctoral Fellowship. Second author supported by NSF grant DMS-0245379.     

An elementary approach to lower bounds in geometric discrepancy

For eachd≥2, it is possible to placen points ind-space so that, given any two-coloring of the points, a half-space exists within which one color outnumbers the other by as much ascn ^1/2−1/2d , for some constantc>0 depending ond. This result was proven in a slightly weaker form by Beck and the bound was later tightened by Alexander. It was recently shown to be asymptotically optimal by Matoušek. We present a proof of the lower bound, which is based on Alexander's technique but is technically simpler and more accessible. We present three variants of the proof, for three diffrent cases, to provide more intuitive insight into the “large-discrepancy” phenomenon. We also give geometric and probabilistic interpretations of the technique. Work by Bernard Chazelle has been supported in part by NSF Grant CCR-90-02352 and The Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc. Work by Jiří Matoušek has been supported by Charles University Grant No. 351, by Czech Republic Grant GAČR 201/93/2167 and in part by DIMACS. Work by Micha Sharir has been supported by NSF Grant CCR-91-22103, by a Max-Planck Research Award, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

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.     

Two combinatorial properties of a class of simplicial polytopes

Letf(P _s ^d ) be the set of allf-vectors of simpliciald-polytopes. ForP a simplicial 2d-polytope let Σ(P) denote the boundary complex ofP. We show that for eachf ∈f(P _s ^d ) there is a simpliciald-polytopeP withf(P)=f such that the 11 02 simplicial diameter of Σ(P) is no more thanf ₀(P)−d+1 (one greater than the conjectured Hirsch bound) and thatP admits a subdivision into a simpliciald-ball with no new vertices that satisfies the Hirsch property. Further, we demonstrate that the number of bistellar operations required to obtain Σ(P) from the boundary of ad-simplex is minimum over the class of all simplicial polytopes with the samef-vector. This polytopeP will be the one constructed to prove the sufficiency of McMullen's conditions forf-vectors of simplicial polytopes.     

All 0–1 polytopes are traveling salesman polytopes

We study the facial structure of two important permutation polytopes in , theBirkhoff orassignment polytopeB _n , defined as the convex hull of alln×n permutation matrices, and theasymmetric traveling salesman polytopeT _n , defined as the convex hull of thosen×n permutation matrices corresponding ton-cycles. Using an isomorphism between the face lattice ofB _n and the lattice of elementary bipartite graphs, we show, for example, that every pair of vertices ofB _n is contained in a cubical face, showing faces ofB _n to be fairly special 0–1 polytopes. On the other hand, we show thatevery 0–1d-polytope is affinely equivalent to a face ofT _n , fordlogn, by showing that every 0–1d-polytope is affinely equivalent to the asymmetric traveling salesman polytope of some directed graph withn nodes. The latter class of polytopes is shown to have maximum diameter [n/3].Partially supported by NSF grant DMS-9207700.