Inequalities forf-vectors of 4-polytopes

LetV, E, S andF be the number of vertices, edges, subfacets and facets, respectively, of a 4-dimensional convex polytope. In this paper we derive new upper and lower bounds forS in terms ofF andV. Research supported by NSF grants GP-27963 and GP-19221.     

On periodically-cyclic Gale 4-polytopes

Based upon a labelling (total ordering) of vertices, a 4-polytope is Gale if the vertices satisfy a part of Gale's Evenness Condition and it is periodically-cyclic if there is an integer k such that every subset of k successive vertices generates a cyclic 4-polytope. Among the bi-cyclic 4-polytopes introduced by Smilansky, we determine which are Gale or periodically-cyclic or both.     

The extended f-vectors of 4-polytopes

For P a d-dimensional convex polytope and S = {i₁,…, i_s} ⊂ {0, 1,…, d−1}, let f_s(P) be the number of chains of faces Ø ⊂ F₁ ⊂ F₂ ⊂ … ⊂ F_s ⊂ P with dim F_j = i_j. By the generalized Dehn-Sommerville equations the dimension of the affine span of the extended f-vectors (f_s(P))_S ⊂ {0,1,2,3} as P ranges over all 4-polytopes is 4, and the extended f-vectors are determined by the values of f₀, f₁, f₂ and f₀₂. Six linear and four nonlinear inequalities on extended f-vectors of 4-polytopes are given. The consequences for the basic f-vector, (f₀, f₁, f₂, f₃), are derived. These include the inequality, 4f₂ ⩾ 3f₀ − 10 + 7f₃, conjectured by Barnette.     

Neighborly 4-polytopes with 9 vertices

A complete classification is given for neighborly 4-polytopes with 9 vertices. It is found that there are exactly 23 combinatorial types.     

Are all simple 4-polytopes Hamiltonian?

We construct an extensive family of non-Hamiltonian, 4-regular, 4-connected graphs and show that none of these graphs is the graph of a simple 4-polytope. Support from NSERC and the Math. Dept. S.F.U. is gratefully acknowledged.     

Long monotone paths on simple 4-polytopes

TheMonotone Upper Bound Problem (Klee, 1965) asks if the maximal numberM(d,n) of vertices in a monotone path along edges of ad-dimensional polytope withn facets can be as large as conceivably possible: IsM(d,n)=M _ubt (d,n), the maximal number of vertices that ad-polytope withn facets can have according to the Upper Bound Theorem?We show that in dimensiond=4, the answer is “yes”, despite the fact that it is “no” if we restrict ourselves to the dual-to-cyclic polytopes. For eachn≥5, we exhibit a realization of a polar-to-neighborly 4-dimensional polytope withn facets and a Hamilton path through its vertices that is monotone with respect to a linear objective function.This constrasts an earlier result, by which no polar-to-neighborly 6-dimensional polytope with 9 facets admits a monotone Hamilton path.     

Ordinary 3-polytopes

We introduce a class of three-dimensional polytopesP with the property that there is a total ordering of the vertices ofP that determines completely the facial structure ofP. This class contains the cyclic 3-polytopes.     

Describing 4-paths in 3-polytopes with minimum degree 5

Back in 1922, Franklin proved that each 3-polytope with minimum degree 5 has a 5-vertex adjacent to two vertices of degree at most 6, which is tight. This result has been extended and refined in several directions. In particular, Jendrol’ and Madaras (1996) ensured a 4-path with the degree-sum at most 23. The purpose of this note is to prove that each 3-polytope with minimum degree 5 has a (6, 5, 6, 6)-path or (5, 5, 5, 7)-path, which is tight and refines both above mentioned results.     

Projections of 3-polytopes

Given any 3-dimensional convex polytopeP, and any simple circuitC in the 1-skeleton ofP, there is a convex polytopeP′ combinatorially equivalent toP, and a direction such that ifP′ is projected orthogonally in this direction, then the inverse image of the boundary of the projection is the circuit inP′ corresponding to the circuitC inP. Research supported by NSF Grant GP-8470.     

An inequality for 3-polytopes

We prove the inequality Σ_n≥7 (n−6) p_n≤v−12 for any 3-dimensional polytope with v vertices and p_n n-sided faces, such that Σ_n≥6 p_n≥3. The polytopes satisfying Σ_n≥7 (n−6) p_n=v−12 are described and an interpretation of our results is given in terms of density of n-sided faces in planar graphs.     

Cyclic coloration of 3-polytopes

A cyclic coloration of a planar graph G is an assignment of colors to the points of G such that for any face bounding cycle the points of F have different colors. We observe that the upper bound 2ρ*(G), due to O. Ore and M. D. Plummer, can be improved to ρ*(G) + 9 when G is 3-connected (ρ* denotes the size of a maximum face). The proof uses two principal tools: the theory of Euler contributions and recent results on contractible lines in 3-connected graphs by K. Ando, H. Enomoto and A. Saito.     

Revlex-initial 0/1-polytopes

We introduce revlex-initial 0/1-polytopes as the convex hulls of reverse-lexicographically initial subsets of 0/1-vectors. These polytopes are special knapsack-polytopes. It turns out that they have remarkable extremal properties. In particular, we use these polytopes in order to prove that the minimum numbers g_nfac(d,n) of facets and the minimum average degree g_avdeg(d,n) of the graph of a d-dimensional 0/1-polytope with n vertices satisfy g_nfac(d,n)?3d and g_avdeg(d,n)?d+4. We furthermore show that, despite the sparsity of their graphs, revlex-initial 0/1-polytopes satisfy a conjecture due to Mihail and Vazirani, claiming that the graphs of 0/1-polytopes have edge-expansion at least one.     

Links and cubic 3-polytopes

It is well known that a prime link diagram corresponds to a signed plane graph without cut vertices (Kauffman, 1989). In this paper, we present a new relation between prime links and cubic 3-polytopes. Let be the set of links such that each has a diagram whose corresponding signed plane graph is the graph of a cubic 3-polytope. We show that all nontrivial prime links, except -torus links and -pretzel links, can be obtained from by using some operation of untwining. Furthermore, we define the generalized cubic 3-polytope chains and then show that any nontrivial link can be obtained from by some untwining operations, where is the set of links corresponding to generalized cubic 3-polytope chains. These results are used to simplify the computation of the Kauffman brackets of links so that the computing can be done in a unified way for many infinite families of links.

     

On realizing symmetric 3-polytopes

We prove the analogue of Eberhard’s Theorem for symmetric convex 3-polytopes with a 4-valent graph, and disprove a conjecture of the late T. Motzkin about realizing symmetric convex 3-polytopes so that all of their geodesics are in planes. This research was supported by the National Research Council of Canada Grant A-3999.     

Equifacetted 3-spheres as topes of nonpolytopal matroid polytopes

We investigate simplicial 3-manifolds, in particular 3-spheres, with few vertices such that the links of all vertices are combinatorially equivalent (equilinked 3-spheres), and, simple 3-manifolds, in particular 3-spheres, with few facets such that all facets are combinatorially equivalent (equifacetted 3-spheres).     

Low minor faces in 3-polytopes

It is trivial that every 3-polytope has a face of degree at most 5, called minor. The height $h\left(f\right)$ of a face $f$ is the maximum degree of the vertices incident with $f$. It follows from the partial double $n$-pyramids that $h\left(f\right)$ can be arbitrarily large for each $f$ if a 3-polytope is allowed to have faces of types $(4,4,\infty )$ or $(3,3,3,\infty )$.In 1996, M. Horňák and S. Jendrol’ proved that every 3-polytope without faces of types $(4,4,\infty )$ and$(3,3,3,\infty )$ has a minor face of height at most 39 and constructed such a 3-polytope satisfying $h\left(f\right)\ge 30$ for all minor faces $f$.The purpose of this paper is to prove that every 3-polytope without faces of types $(4,4,\infty )$ and$(3,3,3,\infty )$ has a minor face of height at most 30, which bound is tight due to the Horňák–Jendrol’ construction.