Contractions to k8

It is proved that the maximal number of edges in a graph with n ≧ 8 vertices that is not contractible to K₈ is 6n ? 21, unless 5 divides n, and the only graphs with n = 5m vertices and more than 6n ? 21 edges that are not contractible to K₈ are the K₅(2)-cockades that have exactly 6n ? 20 edges.     

Path numbers of tournaments

A family of simple (that is, cycle-free) paths is a path decomposition of a tournament T if and only if partitions the acrs of T. The path number of T, denoted pn(T), is the minimum value of | | over all path decompositions of T. In this paper it is shown that if n is even, then there is a tournament on n vertices with path number k if and only if n/2 k n²/4, k an integer. It is also shown that if n is odd and T is a tournament on n vertices, then (n + 1)/2 pn(T) (n² − 1)/4. Moreover, if k is an integer satisfying (i) (n + 1)/2 k n − 1 or (ii) n < k (n² − 1)/4 and k is even, then a tournament on n vertices having path number k is constructed. It is conjectured that there are no tournaments of odd order n with odd path number k for n k < (n² − 1)/4.     

Some Properties of Bell Groups

For any integer n ≠ 0,1, a group G is said to be “n-Bell” if it satisfies the identity [x ⁿ ,y] = [x,y ⁿ ]. It is known that if G is an n-Bell group, then the factor group G/Z ₂(G) has finite exponent dividing 12n ⁵(n ? 1)⁵. In this article we show that this bound can be improved. Moreover, we prove that every n-Bell group is n-nilpotent; consequently, using results of Baer on finite n-nilpotent groups, we give the structure of locally finite n-Bell groups. Finally, we are concerned with locally graded n-Bell groups for special values of n.     

Latin Squares without Orthogonal Mates

In 1779 Euler proved that for every even n there exists a latin square of order n that has no orthogonal mate, and in 1944 Mann proved that for every n of the form 4k + 1, k ≥ 1, there exists a latin square of order n that has no orthogonal mate. Except for the two smallest cases, n = 3 and n = 7, it is not known whether a latin square of order n = 4k + 3 with no orthogonal mate exists or not. We complete the determination of all n for which there exists a mate-less latin square of order n by proving that, with the exception of n = 3, for all n = 4k + 3 there exists a latin square of order n with no orthogonal mate. We will also show how the methods used in this paper can be applied more generally by deriving several earlier non-orthogonality results.     

Odd‐sized partitions of Russell‐sets

In the setting of ZF, i.e., Zermelo–Fraenkel set theory without the Axiom of Choice (AC), we study partitions of Russell‐sets into sets each with exactly n elements (called n ‐ary partitions), for some integer n. We show that if n is odd, then a Russell‐set X has an n ‐ary partition if and only if |X | is divisible by n. Furthermore, we establish that it is relative consistent with ZF that there exists a Russell‐set X such that |X | is not divisible by any finite cardinal n > 1 (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Inertially arbitrary patterns

An n×n sign pattern matrix A is an inertially arbitrary pattern (IAP) if each non-negative triple (r s t) with r+s+t=n is the inertia of a matrix with sign pattern A. This paper considers the n×n(n2) skew-symmetric sign pattern S_n with each upper off-diagonal entry positive, the (1,1) entry negative, the (n n) entry positive, and every other diagonal entry zero. We prove that S_n is an IAP.     

Average-case results on heapsort

A new algorithm for rearranging a heap is presented and analysed in the average case. The average case upper bound for deleting the maximum element of a random heap is improved, and is shown to be less than [logn]+0.299+M(n) comparisons, *) whereM(n) is between 0 and 1. It is also shown that a heap can be constructed using 1.650n+O(logn) comparisons with this algorithm, the best result for any algorithm which does not use any extra space. The expected time to sortn elements is argued to be less thann logn+0.670n+O(logn), while simulation result points at an average case ofn log n+0.4n which will make it the fastest in-place sorting algorithm. The same technique is used to show that the average number of comparisons when deleting the maximum element of a heap using Williams' algorithm for rearrangement is 2([logn]–1.299+L(n)) whereL(n) also is between 0 and 1, and the average cost for Floyd-Williams Heapsort is at least 2nlogn–3.27n, counting only comparisons. An analysis of the number of interchanges when deleting the maximum element of a random heap, which is the same for both algorithms, is also presented.     

A Partition Theory of Planar Animals

A dissection of an animal is a partition of its cells into blocks that are themselves animals. The n-rule allows only those dissections with the area of every block a multiple of n. If an animal with area divisible by n has no dissection allowed by the n-rule, then the animal is said to be an n-irreducible. The partition meet of all allowed dissections of a given animal is called the n-dissection residue of that animal. This paper considers only planar animals. All 2-irreducibles are found, and the problem of computing 2-dissection residues is solved. Two theorems on n-irreducibles are proved. One of them states that large n-irreducibles always arise by adding cells to smaller n-irreducibles.     

Appearance of complex components in a random bigraph

This is an investigation into the limiting distribution of the sparse connected components in an n₁ × n₂ bipartite multigraph with approximately ½n edges, where n₁, n₂ ≈? ½n. We will show that the probability of finding no complex components in a random n₁ × n₂ bigraph, with approximately ½n edges, is asymptotically the same as for random graphs with n vertices and approximately ½n edges, namely √2/3. In addition, we will show that, for n₁ × n₂ multi-bigraphs, the probability distribution for finitely many bicyclic components, tricyclic components, etc., with no components having more than a given number of cycles, asymptotically equals the corresponding distribution for random multigraphs with n vertices and approximately half as many edges. As an application of this analysis we present a method for estimating the efficiency of memory access in a distributed, replicated data base.     

Planar Graphs, via Well-Orderly Maps and Trees

The family of well-orderly maps is a family of planar maps with the property that every connected planar graph has at least one plane embedding which is a well-orderly map. We show that the number of well-orderly maps with n nodes is at most 2^αn+O(logn), where α≈4.91. A direct consequence of this is a new upper bound on the number p(n) of unlabeled planar graphs with n nodes, log₂p(n)≤4.91n. The result is then used to show that asymptotically almost all (labeled or unlabeled), (connected or not) planar graphs with n nodes have between 1.85n and 2.44n edges. Finally we obtain as an outcome of our combinatorial analysis an explicit linear-time encoding algorithm for unlabeled planar graphs using, in the worst-case, a rate of 4.91 bits per node and of 2.82 bits per edge.     

Symmetric Hamilton cycle decompositions of complete graphs minus a 1‐factor

Let n≥2 be an integer. The complete graph K_n with a 1‐factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K_n−F has a decomposition into Hamilton cycles which are symmetric with respect to the 1‐factor F if and only if n≡2, 4 mod 8. We also show that the complete bipartite graph K_{n, n} has a symmetric Hamilton cycle decomposition if and only if n is even, and that if F is a 1‐factor of K_{n, n}, then K_{n, n}−F has a symmetric Hamilton cycle decomposition if and only if n is odd. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:1‐15, 2010     

Fully invariant transformations and associated groups

It is well known that the symmetric group S _ntogether with one idempotent of rank n- 1 on a finite n-element set Nserves as a set of generators for the semigroup T _nof all the total transformations on N. It is also well known that the singular part Sing _n of T _n can be generated by a set of idempotents of rank n- 1. The purpose of this paper is to begin an investigation of the way in which Sing_nand its subsemigroups can be generated by the conjugates of a subset of elements of T _n by a subgroup of S _n . We look for the smallest subset of elements of T _n that will serve and, correspondingly, for a characterization of those subgroups of S _n that will serve. Using some techniques from graph theory we prove our main result:the conjugates of a single transformation of rank n- 1 under Gsuffice to generate Sing_nif and only if Gis what we define to be a 2-block transitive subgroup of S _n .     

Complementary Regions of Knot and Link Diagrams

An increasing sequence of integers is said to be universal for knots and links if every knot and link has a reduced projection on the sphere such that the number of edges of each complementary face of the projection comes from the given sequence. In this paper, it is proved that the following infinite sequences are each universal for knots and links: (3, 5, 7, . . .), (2, n, n + 1, n + 2, . . .) for each n ≥ 3, (3, n, n + 1, n + 2, . . .) for each n ≥ 4. Moreover, the finite sequences (2, 4, 5) and (3, 4, n) for each n ≥ 5 are universal for all knots and links. It is also shown that every knot has a projection with exactly two odd-sided faces, which can be taken to be triangles, and every link of n components has a projection with at most n odd-sided faces if n is even and n + 1 odd-sided faces if n is odd.     

On Generalizations of Prime Ideals (II)

Let R be a commutative ring with identity. We say that a proper ideal P of R is (n ? 1, n)-weakly prime (n ≥ 2) if 0 ≠ a ₁…a _n  ∈ P implies a ₁…a _i?1 a _i+1…a _n  ∈ P for some i ∈ {1,…, n}, where a ₁,…, a _n  ∈ R. In this article, we study (n ? 1, n)-weakly prime ideals. A number of results concerning (n ? 1, n)-weakly prime ideals and examples of (n ? 1, n)-weakly prime ideals are given. Rings with the property that for a positive integer n such that 2 ≤ n ≤ 5, every proper ideal is (n ? 1, n)-weakly prime are characterized. Moreover, it is shown that in some rings, nonzero (n ? 1, n)-weakly prime ideals and (n ? 1, n)-prime ideals coincide.     

On circuits and pancyclic line graphs

Clark proved that L(G) is hamiltonian if G is a connected graph of order n ≥ 6 such that deg u + deg v ≥ n – 1 – p(n) for every edge uv of G, where p(n) = 0 if n is even and p(n) = 1 if n is odd. Here it is shown that the bound n – 1 – p(n) can be decreased to (2n + 1)/3 if every bridge of G is incident with a vertex of degree 1, which is a necessary condition for hamiltonicity of L(G). Moreover, the conclusion that L(G) is hamiltonian can be strengthened to the conclusion that L(G) is pancyclic. Lesniak-Foster and Williamson proved that G contains a spanning closed trail if |V(G)| = n ≥ 6, δ(G) ≥ 2 and deg u + deg v ≥ n – 1 for every pair of nonadjacent vertices u and v. The bound n – 1 can be decreased to (2n + 3)/3 if G is connected and bridgeless, which is necessary for G to have a spanning closed trail.     

A completion problem for finite affine planes

A partial affine plane (PAP) of ordern is ann ²-setS of points together with a collection ofn-subsets ofS called lines such that any two lines meet in at most one point. We obtain conditions under which a PAP with nearlyn ²+n lines can be completed to an affine plane by adding lines. In particular, we make use of Bruck’s completion condition for nets to show that certain PAP’s with at leastn ²+n−√n can be completed and that forn≠3 any PAP withn ²+n−2 lines can be completed.     

Regular<Emphasis Type="Italic">n</Emphasis>-simplices in ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> with vertices in ℤ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

In this paper theI andII regularn-simplices are introduced. We prove that the sufficient and necessary conditions for existence of anI regularn-simplex in ℝ ⁿ are that ifn is even thenn = 4m(m + 1), and ifn is odd thenn = 4m + 1 with thatn + 1 can be expressed as a sum of two integral squares orn = 4m - 1, and that the sufficient and necessary condition for existence of aII regularn-simplex in ℝ ⁿ isn = 2m ² - 1 orn = 4m(m + 1)(m ∈ ℕ). The connection between regularn-simplex in ℝ ⁿ and combinational design is given.     

Plain Bases for Classes of Primitive Recursive Functions

Abasisforaset C of functions on natural numbers is a set F of functions such that C is the closure with respect to substitution of the projection functions and the functions in F. This paper introduces three new bases, comprehending only common functions, for the Grzegorczyk classes ℰⁿ with n ≥ 3. Such results are then applied in order to show that ℰⁿ⁺¹ = K_n for n ≥ 2, where {K_n}_n∈ℕ is the Axt hierarchy.     

The structure and representation of <Emphasis Type="Italic">n</Emphasis>-ary algebras of DNA recombination

In this paper we investigate the structure and representation of n-ary algebras arising from DNA recombination, where n is a number of DNA segments participating in recombination. Our methods involve a generalization of the Jordan formalization of observables in quantum mechanics in n-ary splicing algebras. It is proved that every identity satisfied by n-ary DNA recombination, with no restriction on the degree, is a consequence of n-ary commutativity and a single n-ary identity of the degree 3n-2. It solves the well-known open problem in the theory of n-ary intermolecular recombination.     

Finiteness of integral values for the ratio of two linear recurrences

Let {F(n)} _{n ∈ N} ,{G(n)} _{n ∈ N} , be linear recurrent sequences. In this paper we are concerned with the well-known diophantine problem of the finiteness of the set ? of natural numbers n such that F(n)/G(n) is an integer. In this direction we have for instance a deep theorem of van der Poorten; solving a conjecture of Pisot, he established that if ? coincides with N, then {F(n)/G(n)} _{n ∈ N} is itself a linear recurrence sequence. Here we shall prove that if ? is an infinite set, then there exists a nonzero polynomial P such that P(n)F(n)/G(n) coincides with a linear recurrence for all n in a suitable arithmetic progression. Examples like F(n)=2 ⁿ -2, G(n)=n+2 ⁿ +(-2) ⁿ , show that our conclusion is in a sense best-possible. In the proofs we introduce a new method to cope with a notorious crucial difficulty related to the existence of a so-called dominant root. In an appendix we shall also prove a zero-density result for ? in the cases when the polynomial P cannot be taken a constant. Oblatum 12-XI-2001 & 31-I-2002?Published online: 29 April 2002