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.     

Describing 3-faces in normal plane maps with minimum degree 4

In 1940, Lebesgue proved that every 3-polytope with minimum degree at least 4 contains a 3-face for which the set of degrees of its vertices is majorized by one of the following sequences:

(4,4,∞),(4,5,19),(4,6,11),(4,7,9),(5,5,9),(5,6,7).$(4,4,\infty ),(4,5,19),(4,6,11),(4,7,9),(5,5,9),(5,6,7)\text{.}$

     

The height of faces of 3-polytopes

The height of a face in a 3-polytope is the maximum degree of the incident vertices of the face, and the height of a 3-polytope, h, is the minimum height of its faces. A face is pyramidal if it is either a 4-face incident with three 3-vertices, or a 3-face incident with two vertices of degree at most 4. If pyramidal faces are allowed, then h can be arbitrarily large; so we assume the absence of pyramidal faces. In 1940, Lebesgue proved that every quadrangulated 3-polytope has h ≤ 11. In 1995, this bound was lowered by Avgustinovich and Borodin to 10. Recently, we improved it to the sharp bound 8. For plane triangulation without 4-vertices, Borodin (1992), confirming the Kotzig conjecture of 1979, proved that h ≤ 20 which bound is sharp. Later, Borodin (1998) proved that h ≤ 20 for all triangulated 3-polytopes. Recently, we obtained the sharp bound 10 for triangle-free 3-polytopes. In 1996, Horňák and Jendrol’ proved for arbitrarily 3-polytopes that h ≤ 23. In this paper we improve this bound to the sharp bound 20.     

Joint extension of two theorems of Kotzig on 3-polytopes

The weight of an edge in a graph is the sum of the degrees of its end-vertices. It is proved that in each 3-polytope there exists either an edge of weight at most 13 for which both incident faces are triangles, or an edge of weight at most 10 which is incident with a triangle, or else an edge of weight at most 8. All the bounds 13, 10, and 8 are sharp and attained independently of each other.     

Each Invertible Sharply d-Transitive Finite Permutation Set with d ≥ 4 is a Group

All known finite sharply 4-transitive permutation sets containing the identity are groups, namely S ₄, S ₅, A ₆ and the Mathieu group of degree 11. We prove that a sharply 4-transitive permutation set on 11 elements containing the identity must necessarily be the Mathieu group of degree 11. The proof uses direct counting arguments. It is based on a combinatorial property of the involutions in the Mathieu group of degree 11 (which is established here) and on the uniqueness of the Minkowski planes of order 9 (which had been established before): the validity of both facts relies on computer calculations. A permutation set is said to be invertible if it contains the identity and if whenever it contains a permutation it also contains its inverse. In the geometric structure arising from an invertible permutation set at least one block-symmetry is an automorphism. The above result has the following consequences. i) A sharply 5-transitive permutation set on 12 elements containing the identity is necessarily the Mathieu group of degree 12. ii) There exists no sharply 6-transitive permutation set on 13 elements. For d 6 there exists no invertible sharply d-transitive permutation set on a finite set with at least d + 3 elements. iii) A finite invertible sharply d-transitive permutation set with d 4 is necessarily a group, that is either a symmetric group, an alternating group, the Mathieu group of degree 11 or the Mathieu group of degree 12.     

A (3, 3)-homogeneous quantum logic with 18 atoms. I

A quantum logic is called (m, n)-homogeneous if any its atom is contained exactly in m maximal (with respect to inclusion) orthogonal sets of atoms (we call them blocks), and every block contains exactly n elements. We enumerate atoms by natural numbers. For each block {i, j, k} we use the abbreviation i-j-k. Every such logic has the following 7 initial blocks B ₁, ..., B ₇: 1-2-4-5, 1-6-7, 2-8-9, 2-10-11, 3-12-13, and 3-14-15. For an 18-atom logic the arrangements the rest atoms 16, 17, and 18 is important. We consider the case when they form a loop of order in one of layers composed of initial blocks, for example, l ₄: 3-14-15, 15-16-17, 17-18-13, and 13-12-3. We prove that there exist (up to isomorphism) only 5 such logics, and describe pure states and automorphism groups for them.     

Three Theorems, with Computer-Aided Proofs, on Three-Dimensional Faces and Quotients of Polytopes

We prove that there is a finite list of 3-polytopes so that every rational d -polytope, d ≥ 9 , contains a three-dimensional face in the list. A similar result where ``faces' are replaced by ``quotients' is proved already for (general) 5-polytopes. We also prove that every d -polytope, d ≥ 9 , contains a three-dimensional quotient which is a simplex.     

On 5-isosceles sets in the plane, with linear restriction

A finite planar set is k-isosceles for k≥3 if every k-point subset of the set contains a point equidistant from two others. We show that an 8-set on a line is 5-isosceles if and only if its adjacent interpoint distances are equal to each other, and no 5-isosceles 9-set has 9 points on a line. We also show that the maximum 5-isosceles set with 8 points on a line contains at most 10 points.     

Disjoint 3‐Cycles in Tournaments: A Proof of The Bermond–Thomassen Conjecture for Tournaments

We prove that every tournament with minimum out‐degree at least contains k disjoint 3‐cycles. This provides additional support for the conjecture by Bermond and Thomassen that every digraph D of minimum out‐degree contains k vertex disjoint cycles. We also prove that for every , when k is large enough, every tournament with minimum out‐degree at least contains k disjoint cycles. The linear factor 1.5 is best possible as shown by the regular tournaments.     

Some upper bounds for the diameters of convex polytopes

Δ(d, n) is defined to be the maximum diameter of ad-polytope withn-facets. The main results of the work are an evaluation of Δ(4, 10) and Δ(5, 11). Also, improved upper bounds are found for Δ(6, 13) and Δ(7,14).     

Degree-regular triangulations of torus and Klein bottle

A triangulation of a connected closed surface is called weakly regular if the action of its automorphism group on its vertices is transitive. A triangulation of a connected closed surface is called degree-regular if each of its vertices have the same degree. Clearly, a weakly regular triangulation is degree-regular. In [8], Lutz has classified all the weakly regular triangulations on at most 15 vertices. In [5], Datta and Nilakantan have classified all the degree-regular triangulations of closed surfaces on at most 11 vertices. In this article, we have proved that any degree-regular triangulation of the torus is weakly regular. We have shown that there exists ann-vertex degree-regular triangulation of the Klein bottle if and only if n is a composite number ≥ 9. We have constructed two distinctn-vertex weakly regular triangulations of the torus for eachn ≥ 12 and a (4m + 2)-vertex weakly regular triangulation of the Klein bottle for eachm ≥ 2. For 12 ≤n ≤ 15, we have classified all then-vertex degree-regular triangulations of the torus and the Klein bottle. There are exactly 19 such triangulations, 12 of which are triangulations of the torus and remaining 7 are triangulations of the Klein bottle. Among the last 7, only one is weakly regular.     

Uniform asymptotic expansions of the Pollaczek polynomials

Two uniform asymptotic expansions are obtained for the Pollaczek polynomials P_n(cosθ;a,b). One is for , , in terms of elementary functions and in descending powers of . The other is for , in terms of a special function closely related to the modified parabolic cylinder functions, in descending powers of n. This interval contains a turning point and all possible zeros of P_n(cosθ) in θ(0,π/2].     

Mutually disjoint designs and new 5‐designs derived from groups and codes

The article gives constructions of disjoint 5‐designs obtained from permutation groups and extremal self‐dual codes. Several new simple 5‐designs are found with parameters that were left open in the table of 5‐designs given in (G. B. Khosrovshahi and R. Laue, t‐Designs with t⩾3, in “Handbook of Combinatorial Designs”, 2nd edn, C. J. Colbourn and J. H. Dinitz (Editors), Chapman & Hall/CRC, Boca Raton, FL, 2007, pp. 79–101), namely, 5−(v, k, λ) designs with (v, k, λ)=(18, 8, 2m) (m=6, 9), (19, 9, 7m) (m=6, 9), (24, 9, 6m) (m=3, 4, 5), (25, 9, 30), (25, 10, 24m) (m=4, 5), (26, 10, 126), (30, 12, 440), (32, 6, 3m) (m=2, 3, 4), (33, 7, 84), and (36, 12, 45n) for 2⩽n⩽17. These results imply that a simple 5−(v, k, λ) design with (v, k)=(24, 9), (25, 9), (26, 10), (32, 6), or (33, 7) exists for all admissible values of λ. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 305–317, 2010     

Recognition of finite groups by a set of orders of their elements

For G a finite group, ω(G) denotes the set of orders of elements in G. If ω is a subset of the set of natural numbers, h(ω) stands for the number of nonisomorphic groups G such that ω(G)=ω. We say that G is recognizable (by ω(G)) if h(ω(G))=1. G is almost recognizable (resp., nonrecognizable) if h(ω(G)) is finite (resp., infinite). It is shown that almost simple groups PGL_n(q) are nonrecognizable for infinitely many pairs (n, q). It is also proved that a simple group S₄(7) is recognizable, whereas A₁₀, U₃(5), U₃(7), U₄(2), and U₅(2) are not. From this, the following theorem is derived. Let G be a finite simple group such that every prime divisor of its order is at most 11. Then one of the following holds: (i) G is isomorphic to A₅, A₇, A₈, A₉, A₁₁, A₁₂, L₂(q), q=7, 8, 11, 49, L₃(4), S₄(7), U₄(3), U₆(2), M₁₁, M₁₂, M₂₂, HS, or M^cL, and G is recognizable by the set ω(G); (ii) G is isomorphic to A₆, A₁₀, U₃(3), U₄(2), U₅(2), U₃(5), or J₂, and G is nonrecognizable; (iii) G is isomorphic to S₆(2) or O ₈ ⁺ (2), and h(ω(G))=2. Supported by RFFR grant No. 96-01-01893. Translated fromAlgebra i Logika, Vol. 37, No. 6, pp. 651–666, November–December, 1998.     

Some new designs with prescribed automorphism groups

We establish the existence of simple designs with parameters 2‐(55, 10, 4), 3‐(20, 5, 4), 3‐(21, 7, 30), 4‐(15, 5, 2), 4‐(16, 8, 45), 5‐(16, 7, 10), and 5‐(17, 8, 40), which have previously been unknown. For the corresponding t, v, and k, we study the set of all λ for which simple t‐ designs exist.     

Minimum Degree and Dominating Paths

A dominating path in a graph is a path P such that every vertex outside P has a neighbor on P. A result of Broersma from 1988 implies that if G is an n‐vertex k‐connected graph and , then G contains a dominating path. We prove the following results. The lengths of dominating paths include all values from the shortest up to at least . For , where a is a constant greater than 1/3, the minimum length of a dominating path is at most logarithmic in n when n is sufficiently large (the base of the logarithm depends on a). The preceding results are sharp. For constant s and , an s‐vertex dominating path is guaranteed by when n is sufficiently large, but (where ) does not even guarantee a dominating set of size s. We also obtain minimum‐degree conditions for the existence of a spanning tree obtained from a dominating path by giving the same number of leaf neighbors to each vertex.