On a new class of productive regular Hadamard matrices

We show that for each integer n for which there is a Hadamard matrix of order 4n and 8n²-1 is a prime number, there is a productive regular Hadamard matrix of order 16n²(8n²-1)². As a corollary, by applying a recent result of Ionin, we get many parametrically new classes of symmetric designs whenever either of 4n(8n²-1)-1 or 4n(8n²-1)+1 is a prime power.     

On the 1-factors of n-connected graphs

L. W. Beineke and M. D. Plummer have recently proved [1] that every n-connected graph with a 1-factor has at least n different 1-factors. The main purpose of this paper is to prove that every n-connected graph with a 1-factor has at least as many as n(n − 2)(n − 4) … 4 · 2, (or: n(n − 2)(n − 4) … 5 · 3) 1-factors. The main lemma used is: if a 2-connected graph G has a 1-factor, then G contains a vertex V (and even two such vertices), such that each edge of G, incident to V, belongs to some 1-factor of G.     

Real eigenvalues of nonnegative matrices which commute with a symmetric matrix involution

It is well known that if P is a nonnegative matrix, then its spectral radius is an eigenvalue of P (Perron-Frobenius theorem). In this paper it is shown that if P is an n × n nonnegative matrix and it commutes with a nonnegative symmetric involution when n=4m+3, then (1) P has at least two real eigenvalues if n=4m or 4m + 2, (2) P has at least one real eigenvalue if n=4m+1, and (3) P has at least three real eigenvalues if n=4m+3, where m is a nonnegative integer and n ? 1. Examples are given to show that these results are the best possible, and nonnegative symmetric involutions are classified.     

The size of chordal,interval and threshold subgraphs

Given a graphG withn vertices andm edges, how many edges must be in the largest chordal subgraph ofG? Form=n ²/4+1, the answer is 3n/2?1. Form=n ²/3, it is 2n?3. Form=n ²/3+1, it is at least 7n/3?6 and at most 8n/3?4. Similar questions are studied, with less complete results, for threshold graphs, interval graphs, and the stars on edges, triangles, andK ₄'s.     

The rigidity of Clifford torusS^1 \left( {\sqrt {\frac{1}{n}} } \right) \times S^{n - 1} \left( {\sqrt {\frac{{n - 1}}{n}} } \right)

In this paper, we prove that ifM is ann-dimensional closed minimal hypersurface with two distinct principal curvatures of a unit sphereS ⁿ⁺¹ (1), thenS=n andM is a Clifford torus ifn≤S≤n+[2n ²(n+4)/3(n(n+4)+4)], whereS is the squared norm of the second fundamental form ofM.     

A note on asymptotic values of quasiregular maps

In this note we give an example of a quasiregular map in ? ⁿ (n ≥ 3) of order of growth n ? 1 and whose set of asymptotic values is A ∪ {∞} for a given Suslin analytic set A ? ? ⁿ . Our example is a modification of Drasin’s construction in [4] of a quasiregular map with order of growth n ? 1 and set of asymptotic values ? ⁿ ∪ {∞}.     

P 4k−1-factorization of bipartite multigraphs

Let λK _m,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A P _v-factorization of λK _m,n is a set of edge-disjoint P _v -factors of λK _m,n which partition the set of edges of λK _m,n. When v is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P _v -factorization of λK _m,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true for v = 3. In this paper we will show that the conjecture is true when v = 4k ? 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P _4k?1-factorization of λK _m,n is (1) (2k ? 1)m ? 2kn, (2) (2k ? 1)n ? 2km, (3) m + n ≡ 0 (mod 4k ? 1), (4) λ(4k ? 1)mn/[2(2k ? 1)(m + n)] is an integer.     

Decomposition of complete multigraphs into crown graphs

Let λ K _v be the complete multigraph, G a finite simple graph. A G-design of λ K _v is denoted by GD(v,G,λ). The crown graph Q _n is obtained by joining single pendant edge to each vertex of an n-cycle. We give new constructions for Q _n -designs. Let v and λ be two positive integers. For n=4, 6, 8 and λ≥1, there exists a GD(v,Q _n ,λ) if and only if either (1) v>2n and λ v(v?1)≡0 (mod 4n), or (2) v=2n and λ≡0 (mod 4). Let n≥4 be even. Then (1) there exists a GD(2n,Q _n ,λ) if and only if λ≡0 (mod 4). (2) There exists a GD(2n+1,Q _n ,λ) when λ≡0 (mod 4).     

Even permutations as a product of two elements of order five

Let A_n denote the alternating group on n symbols. If n = 5, 6, 7, 10, 11, 12, 13 or n ⩾ 15, every permutation in A_n is the product of two elements of order 5 in A_n. The same is true for n ⩽ 14, except for thirteen types of permutations, namely 3¹, 2², 2⁴, 3³, 2¹3¹4¹, 2²5¹, 2⁵4¹, 1¹, 1², 1³, 1⁴, 3¹1¹, 2⁴1¹. (For example, the permutation (12)(34)(56)(78)(9) is not the product of two elements of order 5 in A₉.)     

Positive integers expressible as a sum of three squares in essentially only one way

The set S consisting of those positive integers n which are uniquely expressible in the form n = a² + b² + c², $\text{a ≧ b ≧ c ≧ 0}$, is considered. Since n ∈ S if and only if 4n ∈ S, we may restrict attention to those n not divisible by 4. Classical formulas and the theorem that there are only finitely many imaginary quadratic fields with given class number imply that there are only finitely many n ∈ S with n = 0 (mod 4). More specifically, from the existing knowledge of all the imaginary quadratic fields with odd discriminant and class number 1 or 2 it is readily deduced that there are precisely twelve positive integers n such that n ∈ S and n ≡ 3 (mod 8). To determine those n ∈ S such that n ≡ 1, 2, 5, 6 (mod 8) requires the determination of the imaginary quadratic fields with even discriminant and class number 1, 2, or 4. While the latter information is known empirically, it has not been proved that the known list of 33 such fields is complete. If it is complete, then our arguments show that there are exactly 21 positive integers n such that n ∈ S and n ≡ 1, 2, 5, 6 (mod 8).     

Generalized Latin squares of order n with n 2 − 1 distinct elements

Let n ≥ 3 be a positive integer. We show that the number of equivalence classes of generalized Latin squares of order n with n ² ? 1 distinct elements is 4 if n = 3 and 5 if n ≥ 4. It is also shown that all these squares are embeddable in groups. As an application, we obtain a lower bound for the number of isomorphism classes of certain Eulerian graphs with n ² + 2n ? 1 vertices.     

Existence of weakly pandiagonal orthogonal Latin squares

A weakly pandiagonal Latin square of order n over the number set {0, 1, . . . , n-1} is a Latin square having the property that the sum of the n numbers in each of 2n diagonals is the same. In this paper, we shall prove that a pair of orthogonal weakly pandiagonal Latin squares of order n exists if and only if n ≡ 0, 1, 3 (mod 4) and n≠3.     

Two conjectures of Grünbaum on arrangements of curves

We prove the following two conjectures of Grünbaum on arrangements of curves in the Euclidean plane: (a) There is no arrangement of n curves such that 4n - 4<f₂(A)<5n - 12. (b) There is no digon-free arrangement of n curves (n?36) such that 4n - 4<f₂(A)<5n - 7. (f₂(A) denotes the number of faces of the arrangement A.) Generalizing (a). we obtain: (c) For each k there is an integer n₀ (depending on k) such that no arrangement of n curves (n ? n₀) satisfies: kn-2k+4<f₂(A)<(k+1)n-k(k-1).     

Heights of representative systems

Representative systems are hierarchical aggregation schemes that are applicable in social choice theory, multiattribute decision making, and in the study of three-valued logics. For example, many procedures for voting on issues—including simple majority voting and weighted voting—can be characterized as representative system. Such systems also include procedures in which vote outcomes of constituencies are treated as votes in a higher level of an election system. The general form of a representative system consists of a “supreme council” which aggregates vote outcomes of secondary councils, which in turn aggregate vote outcomes of tertiary councils, and so forth.An n-variable representative system maps n-tuples of 1's, 0's and ?1's into {1,0,?1} through a nested hierarchy of sign functions. The height of a representative system is the fewest number of hierarchical levels that are needed to characterize the system. The height μ(n) of all n-variable representative systems is the largest height of such systems. It was shown previously that μ(n) ? n ? 1 for all positive integers n and that μ(n) = n ? 1 for n from 1 to 4 inclusive. The present paper proves that μ(5) = μ(6) = 4 and that μ(n) ? ?2 for all n ? 6. The height function μ is known to be unbounded.     

Shortest string containing all permutations

In this paper, we consider the problem of constructing a shortest string of {1,2,…,n} containing all permutations on n elements as subsequences. For example, the string 1 2 1 3 1 2 1 contains the 6 (=3!) permutations of {1,2,3} and no string with less than 7 digits contains all the six permutations. Note that a given permutation, such as 1 2 3, does not have to be consecutive but must be from left to right in the string.We shall first give a rule for constructing a string of {1,2,…,n} of infinite length and the show that the leftmost n²?2n+4 digits of the string contain all the n! permutations (for n≥3). We conjecture that the number of digits f(n) = n²?2n+4 (for n≥3) is the minimum.Then we study a new function F(n,k) which is the minimum number of digits required for a string of n digits to contain all permutations of i digits, i≤k. We conjecture that F(n,k) = k(n?1) for 4≤k ≤n?1.     

Sets of permutations that generate the symmetric group pairwise

The paper contains proofs of the following results. For all sufficiently large odd integers n, there exists a set of ²n−1 permutations that pairwise generate the symmetric group Sn. There is no set of ²n−1+1 permutations having this property. For all sufficiently large integers n with n≡2mod4, there exists a set of ²n−2 even permutations that pairwise generate the alternating group An. There is no set of ²n−2+1 permutations having this property.     

Near-boolean algebras I: Combinatorial aspects

An algebra $\textcolor{red}{}\text{=(A; ?, ?, ′, 0, 1)}$ is near-boolean if every two generated subalgebra is a boolean algebra. It is shown that for n ? 4 there is a near-boolean algebra of size n ≡ 4 or 8 (mod 12), that for n ? 16 and n ≡ 4 or 8 (mod 12) there is a near-boolean algebra of size n which is not a boolean algebra, and that the smallest near-boolean algebra which is not a boolean algebra has 16 elements.     

Author index for volume 39

The distribution γ(c, n) of de Bruijn sequences of order n and linear complexity c is investigated. Some new results are proved on the distribution of de Bruijn sequences of low complexity, i.e., their complexity is between 2^n?1 + n and 2^n?1 + 2^n?2. It is proved that for n ? 5 and 2^n?1 + n?c<2^n?1 + 2^n?2, γ(c, n) ≡ 0 (mod 4). It is shown that for n ? 11, γ(2^n?1 + n, n) > 0. It is also proved that γ(2^n?1 + 2^n?2, n) ? 4γ(2^n?2 ? 1, n ? 2) and we give a recursive method to generate de Bruijn sequences of complexity 2^n?1 + 2^n?2.     

A note on cake cutting

The algorithmic aspects of the following problem are investigated: n (≥2) persons want to cut a cake into n shares so that every person will get at least 1/n of the cake by his own measure and so that the number of cuts made on the cake is minimal. The cutting process is to be governed by a protocol (computer program). It is shown that no deterministic protocol exists which is fair (in a sense defined in the text) and results in at most n ? 1 cuts. An O(n log n)-cut deterministic protocol and an O(n)-cut randomized protocol are given explicitly and a deterministic fair protocol with 4 cuts for n=4 is described in the appendix.     

On isomorphisms of circulant digraphs of bounded degree

C.H. Li recently made the following conjecture: Let Γ be a circulant digraph of order n=n₁n₂ and degree m, where gcd(n₁,n₂)=1, n₁ divides 4k, where k is odd and square-free, and every prime divisor of n₂ is greater than m, or, if Γ is a circulant graph, every prime divisor of n₂ is greater than 2m. Then Γ is a CI-digraph of Z_n. In this paper we verify that this conjecture is true.