Cyclic Degrees of 3-Polytopes

 A precise upper bound is obtained for the minimum cyclic vertex degree in a 3-polytope with specified maximum face size. This implies improvements to some known upper bounds for the cyclic chromatic numbers of 3-polytopes. Received: August 18, 1997 Revised: August 24, 1998     

Heights of Minor Faces in 3-Polytopes

Siberian Mathematical Journal - Each 3-polytope has obviously a face  $ f $ of degree $ d(f) $ at most 5 which is called minor. The height $ h(f) $ of $ f $ is...     

Small Embeddings of Partial Steiner Triple Systems

It was proved in 2009 that any partial Steiner triple system of order u has an embedding of order v for each admissible . This result is best possible in the sense that, for each , there exists a partial Steiner triple system of order u that does not have an embedding of order v for any . Many partial Steiner triple systems do have embeddings of orders smaller than , but much less is known about when these embeddings exist. In this paper, we detail a method for constructing such embeddings. We use this method to show that each member of a wide class of partial Steiner triple systems has an embedding of order v for at least half (or nearly half) of the orders for which an embedding could exist. For some members of this class we are able to completely determine the set of all orders for which the member has an embedding.     

Discretely Compact Embeddings of Spaces of Cell-Centered Grid Functions

Compactness of embeddings in discrete counterparts of Sobolev spaces is considered. We study the embeddings in spaces of cell-centered grid functions, in one- and two-dimensional domains. No restrictions are made on the mesh-ratios of the underlying meshes.     

A Structural Property of Convex 3-Polytopes

In this paper we prove that each convex 3-polytope contains a path on three vertices with restricted degrees which is one of the ten types. This result strengthens a theorem by Kotzig that each convex 3-polytope has an edge with the degree sum of its end vertices at most 13.     

Minimal Simplicial Dissections and Triangulations of Convex 3-Polytopes

This paper addresses three questions related to minimal triangulations of a three-dimensional convex polytope P . • Can the minimal number of tetrahedra in a triangulation be decreased if one allows the use of interior points of P as vertices? • Can a dissection of P use fewer tetrahedra than a triangulation? • Does the size of a minimal triangulation depend on the geometric realization of P ? The main result of this paper is that all these questions have an affirmative answer. Even stronger, the gaps of size produced by allowing interior vertices or by using dissections may be linear in the number of points. Received August 16, 1999, and in revised form February 29, 2000. Online publication May 19, 2000.     

Polytopal Linear Groups and Balanced 3-Polytopes

In [5 Bruns , W. , Gubeladze , J. ( 2002 ). Polyhedral K ₂ . Manuscr. Math. 109 : 367 – 404 . [Google Scholar]] Bruns and Gubeladze have constructed Milnor K ₂-groups for so-called balanced lattice polytopes and classified the balanced polytopes of dimension 2 up to equivalence of the stable elementary groups 𝔼(R, P). In [6 Bruns , W. , Gubeladze , J. ( 2003 ). Higher polyhedral K-groups . J. Pure and Applied Algebra 184 : 175 – 228 .[Crossref] , [Google Scholar]] they have shown that the polytopes in a certain subclass, called Col-divisible, behave well for the construction of higher K-groups. In this article, we give a list of all possibly occurring E-equivalence classes of three-dimensional balanced polytopes. Finally, we compute 𝔼(R, P) provided P is a Col-divisible balanced polytope of dimension three.     

Low Faces of Restricted Degree in 3-Polytopes

Siberian Mathematical Journal - The degree of a vertex or face in a 3-polytope is the number of incident edges. A k-face is one of degree k, a k−-face has degree at most k. The height of a...     

Shelling Polyhedral 3-Balls and 4-Polytopes

There is a long history of constructions of nonshellable triangulations of three-dimensional (topological) balls. This paper gives a survey of these constructions, including Furch's 1924 construction using knotted curves, which also appears in Bing's 1962 survey of combinatorial approaches to the Poincaré conjecture, Newman's 1926 explicit example, and M. E. Rudin's 1958 nonshellable triangulation of a tetrahedron with only 14 vertices (all on the boundary) and 41 facets. Here an (extremely simple) new example is presented: a nonshellable simplicial three-dimensional ball with only 10 vertices and 21 facets. It is further shown that shellings of simplicial 3 -balls and 4 -polytopes can ``get stuck': simplicial 4 -polytopes are not in general ``extendably shellable.' Our constructions imply that a Delaunay triangulation algorithm of Beichl and Sullivan, which proceeds along a shelling of a Delaunay triangulation, can get stuck in the three-dimensional version: for example, this may happen if the shelling follows a knotted curve. Received November 21, 1995, and in revised form September 20, 1996.     

On the Buchstaber Invariant of Simple Convex 3-Polytopes

In this paper the author gives a method of constructing characteristic matrices,and uses it to determine the Buchstaber invariants of all simple convex 3-polytopes,which imply that each simple convex 3-polytope admits a characteristic function.As a further application of the method,the author also gives a simple new proof of five-color theorem.     

Approximation for Minimum Triangulations of Simplicial Convex 3-Polytopes

A minimum triangulation of a convex 3-polytope is a triangulation that contains the minimum number of tetrahedra over all its possible triangulations. Since finding minimum triangulations of convex 3-polytopes was recently shown to be NP-hard, it becomes significant to find algorithms that give good approximation. In this paper we give a new triangulation algorithm with an improved approximation ratio 2 - Ω(1/\sqrt n ) , where n is the number of vertices of the polytope. We further show that this is the best possible for algorithms that only consider the combinatorial structure of the polytopes. Received August 5, 2000, and in revised form March 29, 2001, and May 3, 2001. Online publication October 12, 2001.     

Grid Orientations, (d,d + 2)-Polytopes, and Arrangements of Pseudolines

We investigate the combinatorial structure of linear programs on simple d-polytopes with d + 2 facets. These can be encoded by admissible grid orientations. Admissible grid orientations are also obtained through orientation properties of a planar point configuration or by the dual line arrangement. The point configuration and the polytope corresponding to the same grid are related through an extended Gale transform. The class of admissible grid orientations is shown to contain nonrealizable examples, i.e., there are admissible grid orientations which cannot be obtained from a polytope or a point configuration. It is shown, however, that every admissible grid orientation is induced by an arrangement of pseudolines. This later result is used to prove several nontrivial facts about admissible grid orientations.     

3-Colorable Even Embeddings on Closed Surfaces

It is known that for any closed surface F², every even embedding on F² with sufficiently large representativity is 4-colorable. In this paper, we shall characterize 3-colorable even embeddings on F² with sufficiently large representativity.     

Linkless and Flat Embeddings in 3-Space

We consider piecewise linear embeddings of graphs in 3-space ℝ³. Such an embedding is linkless if every pair of disjoint cycles forms a trivial link (in the sense of knot theory). Robertson, Seymour and Thomas (J. Comb. Theory, Ser. B 64:185–227, 1995) showed that a graph has a linkless embedding in ℝ³ if and only if it does not contain as a minor any of seven graphs in Petersen’s family (graphs obtained from K ₆ by a series of YΔ and ΔY operations). They also showed that a graph is linklessly embeddable in ℝ³ if and only if it admits a flat embedding into ℝ³, i.e. an embedding such that for every cycle C of G there exists a closed 2-disk D⊆ℝ³ with D∩G=∂D=C. Clearly, every flat embedding is linkless, but the converse is not true. We consider the following algorithmic problem associated with embeddings in ℝ³:     

Convex Drawings of Planar Graphs and the Order Dimension of 3-Polytopes

We define an analogue of Schnyder's tree decompositions for 3-connected planar graphs. Based on this structure we obtain: Let G be a 3-connected planar graph with f faces, then G has a convex drawing with its vertices embedded on the (f–1)×(f–1) grid. Let G be a 3-connected planar graph. The dimension of the incidence order of vertices, edges and bounded faces of G is at most 3.The second result is originally due to Brightwell and Trotter. Here we give a substantially simpler proof.     

Embeddings in the 3/4 range

We give a complete obstruction to turning an immersion f:M^m→Rⁿ into an embedding when 3n?4m+5. It is a secondary obstruction, and exists only when the primary obstruction, due to André Haefliger, vanishes. The obstruction lives in a twisted cobordism group, and its vanishing implies the existence of an embedding in the regular homotopy class of f in the range indicated. We use Tom Goodwillie's calculus of functors, following Michael Weiss, to help organize and prove the result.     

Convex Embeddings and Bisections of 3-Connected Graphs1

Given two disjoint subsets T ₁ and T ₂ of nodes in an undirected 3-connected graph G = (V, E) with node set V and arc set E, where and are even numbers, we show that V can be partitioned into two sets V ₁ and V ₂ such that the graphs induced by V ₁ and V ₂ are both connected and holds for each j = 1,2. Such a partition can be found in time. Our proof relies on geometric arguments. We define a new type of convex embedding of k-connected graphs into real space R ^k-1 and prove that for k = 3 such an embedding always exists. ¹ A preliminary version of this paper with title Bisecting Two Subsets in 3-Connected Graphs appeared in the Proceedings of the 10th Annual International Symposium on Algorithms and Computation, ISAAC 99, (A. Aggarwal, C. P. Rangan, eds.), Springer LNCS 1741, 425–434, 1999.     

Describing Neighborhoods of 5-Vertices in a Class of 3-Polytopes with Minimum Degree 5

Lebesgue proved in 1940 that each 3-polytope with minimum degree 5 contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences(6, 6, 7, 7, 7), (6, 6, 6, 7, 9), (6, 6, 6, 6, 11)(5, 6, 7, 7, 8), (5, 6, 6, 7, 12), (5, 6, 6, 8, 10), (5, 6, 6, 6, 17)(5, 5, 7, 7, 13), (5, 5, 7, 8, 10), (5, 5, 6, 7, 27), (5, 5, 6, 6,∞), (5, 5, 6, 8, 15), (5, 5, 6, 9, 11)(5, 5, 5, 7, 41), (5, 5, 5, 8, 23), (5, 5, 5, 9, 17), (5, 5, 5, 10, 14), (5, 5, 5, 11, 13).We prove that each 3-polytope with minimum degree 5 without vertices of degree from 7 to 10 contains a 5-vertex whose set of degrees of its neighbors is majorized by one of the following sequences: (5, 6, 6, 5, ∞), (5, 6, 6, 6, 15), and (6, 6, 6, 6, 6), where all parameters are tight.