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     

Small Grid Embeddings of 3-Polytopes

We introduce an algorithm that embeds a given 3-connected planar graph as a convex 3-polytope with integer coordinates. The size of the coordinates is bounded by O(2^7.55n )=O(188 ⁿ ). If the graph contains a triangle we can bound the integer coordinates by O(2^4.82n ). If the graph contains a quadrilateral we can bound the integer coordinates by O(2^5.46n ). The crucial part of the algorithm is to find a convex plane embedding whose edges can be weighted such that the sum of the weighted edges, seen as vectors, cancel at every point. It is well known that this can be guaranteed for the interior vertices by applying a technique of Tutte. We show how to extend Tutte’s ideas to construct a plane embedding where the weighted vector sums cancel also on the vertices of the boundary face.     

凸正多胞体的自同构群的一个刻画

确定图和各种组合结构的自同构群历来是组合数学中重要且困难的问题.利用图的基本理论和置换群的一些初等结果对全体凸正多胞体的自同构群给出一个新的刻画.     

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...     

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.     

Resolvable Coverings of 2-Paths by Cycles

 Let K _n be the complete graph on n vertices. A C(n,k,λ) design is a multiset of k-cycles in K _n in which each 2-path (path of length 2) of K _n occurs exactly λ times. A C(lk,k,1) design is resolvable if its k-cycles can be partitioned into classes so that every vertex appears exactly once in each class. A C(n,n,1) design gives a solution of Dudeney's round table problem. It is known that there exists a C(n,n,1) design when n is even and there exists a C(n,n,2) design when n is odd. In general the problem of constructing a C(n,n,1) design is still open when n is odd. Necessary and sufficient conditions for the existence of C(n,k,λ) designs and resolvable C(lk,k,1) designs are known when k=3,4. In this paper, we construct a resolvable C(n,k,1) design when n=p ^e +1 ( p is a prime number and e≥1) and k is any divisor of n with k≠1,2. Received: October, 2001 Final version received: September 4, 2002 RID="*" ID="*" This research was supported in part by Grant-in-Aid for Scientific Research (C) Japan     

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.     

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...     

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.     

A Note on the Jones Polynomials of 3-Braid Links

Siberian Mathematical Journal - The braid group on $ n $ strands plays a central role in knot theory and low dimensional topology. 3-braids were classified, up to conjugacy, into normal forms....     

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.     

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.     

A Semilattice of Degrees of Computable Metrics

Siberian Mathematical Journal - Under study is the ordering $ {mathcal{CM}}_{c}({mathbf{X}}) $ of $ c $ -degrees of computable metrics on a Polish space  $ {mathbf{X}} $ with...     

纵横步进编织规律的数学描述及其证明

对于纵横编织步进编织中的步长选取规律用精确的数学语言描述 ,并给出其严格的数学证明 ,为进一步设计和实现纵横编织技术提供了理论基础 .     

A Separation Property of the Observer-Based Stabilizing Controller for Linear Delay Systems

Siberian Mathematical Journal - This paper is concerned with the observer-based controller for the stabilization of linear systems with multiple delays. We design a state observer for the...     

Skew-product decompositions of Brownian motions on manifolds: A probabilistic aspect of the Lichnerowicz-Szabo theorem

We show that the only compact simply connected manifolds for which the radial part of Brownian motion enjoys the Markov property are compact two points homogeneous spaces, i.e. rank one symmetric spaces.     

Generic Immersions of the Two-Sphere to R<Superscript>3</Superscript> and Their Skeletons

Let f:S ² ↬ R ³ be a generic smooth immersion. The skeleton of f is the following triple (Γ, D, p): Γ ⊂ R ³ is the 1-polyhedron of singular points of f, D = f⁻¹(Γ) ⊂ S ² is also a 1-polyhedron, and p : D → Γ, x ↦ f(x), is the projection. For triples of the form (D,Γ,p), where Γ has at most four vertices, we give an iff-condition under which the triple is the skeleton of a smooth immersion f : S ² ↬ R ³. Bibliography: 4 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 299, 2003, pp. 300–313.     

A New Characterization of Simple K 3-Groups by Their Orders and Large Degrees of Their Irreducible Characters

It is a well-known fact that characters of a finite group can give important information of the structure of the group. Also it was proved by the second author that a finite simple group can uniquely determined by its character table. Here the authors attempt to investigate how to characterize a finite group by using less information of its character table, and successfully characterize K ₃-groups by their orders and one or two irreducible character degrees of their character tables.