The existence of Howell designs of even side

A Howell design of side s and order 2n, or more briefly, an H(s, 2n), is an s × s array in which each cell either is empty or contains an unordered pair of elements from some 2n-set, say X, such that (i) each row and column is Latin (that is, every element of X is in precisely one cell of each row and column) and (ii) any unordered pair of elements of X is in at most one cell of the array. A necessary condition for the existence of an H(s, 2n) is that n = 0 or n ? s ? 2n ?1. An $\text{H}{}^1\text{(s, 2n)}$ is an H(s, 2n) in which there is a subset of X, say Y, of cardinality 2n ? s such that no pair of elements from Y is in any cell of the array. In this paper it is shown that if s is an even positive integer, if s and n satisfy the necessary condition and if (s, 2n) ≠ (2, 4) or (6, 12), then there is an $\text{H}{}^1\text{(s, 2n)}$; furthermore, there is no H(2, 4) nor any $\text{H}{}^1\text{(6,12)}$ though there is an H(6, 12).     

A doubly divisible nearly Kirkman system

In this note we exhibit an example of a new class of combinatorial array. A Room square [9] is an r × r square each of whose cells is either empty or contains a distinct unordered pair with entries from the set of integers {1, 2,…, r + 1} such that each integer appears exactly once in each row and exactly once in each column. We present an analogous square whose entries are unordered triples, none of whose two-element subsets is repeated.     

The existence of howell designs of siden+1 and order 2n

AHowell design of side s andorder 2n, or more briefly, anH(s, 2n), is ans×s array in which each cell either is empty or contains an unordered pair of elements from some 2n-set, sayX, such that (a) each row and each column is Latin (that is, every element ofX is in precisely one cell of each row and each column) and (b) every unordered pair of elements fromX is in at most one cell of the array. Atrivial Howell design is anH(s, 0) havingX=? and consisting of ans×s array of empty cells. A necessary condition onn ands for the existence of a nontrivialH(s, 2n) is that 0<n≦s≦2n-1. AnH(n+t, 2n) is said to contain a maximum trivial subdesign if somet×t subarray is theH(t, 0). This paper describes a recursive construction for Howell designs containing maximum trivial subdesigns and applies it to settle the existence question forH(n+1, 2n)’s: forn+1 a positive integer, there is anH(n+1, 2n) if and only ifn+1 ∉ {2, 3, 5}.     

The existence of Howell designs of odd side

Three recursive constructions for Howell designs are described, and it is shown that all Howell designs H(s, 2n) exist, with s odd, n ? s ? 2n ? 1, (s, 2n) ≠ (3, 4), (5, 6), or (5, 8). This settles the existence question for Howell designs of odd side.     

An infinite class of generalized room squares

A generalized Room square $\text{G}$ of order n and degree k is an ${}^{\mathrm{n?1}}{}^{\mathrm{k?1}}\text{×}{}^{\mathrm{n?1}}{}^{\mathrm{k?1}}$ array, each cell of which is either empty or contains an unordered k-tuple of a set S, |S| = n, such that each row and each column of the array contains each element of S exactly once and $\text{G}$ contains each unordered k-tuple of S exactly once. Using a class of Steiner systems and a generalized Room square of order 18 and degree 3 constructed by ad hoc methods, an infinite class of degree 3 squares is constructed.     

Row complete squares and a problem of A. Kotzig concerning P-quasigroups and eulerian circuits

An n × n square L on n symbols is called row (column) complete if every ordered pair of the symbols of L occurs just once as an adjacent pair of elements in some row (column) of L. It is called row (column) latin if each symbol occurs exactly once in each row (column) of the square. A square which is both row latin and column latin is called a latin square. All known examples of row complete latin squares can be made column complete as well by suitable reordering of their rows and in the present paper we provide a sufficient condition that a given row complete latin square should have this property.Using row complete and column latin squares as a tool we follow this by showing how to construct code words on n symbols of the maximum possible length $\text{l =}\text{1}\text{2}\text{n(n ? 1) + 1}$ with the two properties that (i) no unordered pair of consecutive symbols is repeated more than once and (ii) no unordered pair of nearly consecutive symbols is repeated more than once. (Two symbols are said to be nearly consecutive if they are separated by a single symbol.) We prove that such code words exist whenever n = 4r + 3 with r ? 1 mod 6 and r ? 2 mod 5. We show that the existence of such a code word for a given value of n guarantees the existence of an Eulerian circuit in the complete undirected n-graph which corresponds to a P-quasigroup, thus answering a question raised by A. Kotzig in the affirmative. (Kotzig has defined a P-groupoid as a groupoid (G, ·) having the following three properties: (i) a . a = a for all a?G; (ii) a ≠ b implies a ≠ a . b and b ≠ a. b for all a, b?G; and (iii) a . b = c implies c. b = a for all a, b, c?G. Every decomposition of the complete undirected n-graph into disjoint closed circuits defines such a P-groupoid, as is easily seen by defining a . b = c if and only if a, b, c are consecutive edges of one such closed circuit. A P-groupoid whose multiplication table is a latin square is called a P-quasigroup.)     

Doubly diagonal orthogonal latin squares

A pair of doubly diagonal orthogonal latin squares of order n, DDOLS(n), is a pair of orthogonal latin squares of order n with the property that each square has a transversal on both the front diagonal (the cells {(i, i):1?i?n}) and the back diagonal (the cells {(i, n + 1?i): 1?i?n}). We show that for all n except n = 2, 3, 6, 10, 12, 14, 15, 18 and 26, there exists a pair of DDOLS(n). Obbviously these do not exist when n = 2, 3 and 6.     

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.     

New constructions for balanced Howell rotations

Howell rotations have been used in bridge tournaments for a long time. But it was not until 1955 that Parker and Mood first gave a rigorous definition of a balanced Howell rotation and began a systematic study of its mathematical properties. Later, Berlekamp and Hwang extended this work to the study of complete balanced Howell rotations (which are special cases of balanced Howell rotations). Surprisingly, even though the concept of balanced Howell rotations precedes that of complete balanced Howell rotations, systematic construction methods have been studied only for the latter. Most of these construction methods use the properties of a Galois field GF(p^γ) where p^γ is a prime power. In this paper, we use the properties of a Galois domain GD(p^γq^s) to construct balanced Howell rotations for n partnerships where n ? 1 is the product of two prime powers satisfying certain conditions. In particular, we construct a balanced Howell rotation for 36 partnerships, this being the smallest number for which the existence of a balanced Howell rotation was not previously known. We also give two composition methods for the constructions of balanced Howell rotations.     

A construction method for generalized Room squares

A Generalized Room Square (GRS) of ordern and degreek is an \(\left( {\begin{array}{*{20}c} {n - 1} \\ {k - 1} \\ \end{array} } \right) \times \left( {\begin{array}{*{20}c} {n - 1} \\ {k - 1} \\ \end{array} } \right)\) array of which each cell is either empty or contains an unorderedk-tuple of a setS, |S|=n, such that each row and each column of the array contains each element ofS exactly once and the array contains each unorderedk-tuple exactly once. A method of generating the unordered triples on the setS=GF(q) ? {∞} is given, 3 ∣ (q ∣ 1). This method is used to construct GRS's of appropriate ordern and degree 3, for alln<50.     

New classes of complete balanced Howell rotations

Complete balanced Howell rotations (CBHR) owe their origins to duplicate bridge tournaments but have since been shown to possess of deep combinatorial properties. They include many other combinatorial designs as special cases, such as: balanced Howell rotations, weak complete balanced Howell rotations, Room squares, Howell designs, and a class of balanced incomplete block designs.All known CBHR's are for n partnerships such that n = 2^t(p^r + 1), where p^r is an odd prime power and t a natural number. In most cases, p^r ≡ 3(mod 4) is also assumed. Berlekamp and Hwang gave constructions of CBHR's for each such n > 3 with t = 0; Schellenberg gave constructions for each such n with t = 1. In this paper, we construct CBHR for each such n with t arbitrary.     

The skew chromatic index of a graph

We define a skew edge coloring of a graph to be a set of two edge colorings such that no two edges are assigned the same unordered pair of colors. The skew chromatic index s(G) is the minimum number of colors required for a skew edge coloring of G. We show that this concept is closely related to that of skew Room squares and use this relation to prove that s(G) is at most o(G) + 4. We also find better upper bounds for s(G) when G is cyclic, cubic, or bipartite. In particular we use a construction involving Latin squares to show that if G is complete bipartite of order 2n, s(G) is bounded above by roughly $\text{3n}\text{2}$.     

There are no de bruijn sequences of span n with complexity 2n − 1 + n + 1

If s = (s₀, s₁,…, s_2ⁿ?1) is a binary de Bruijn sequence of span n, then it has been shown that the least length of a linear recursion that generates s, called the complexity of s and denoted by c(s), is bounded for n ? 3 by 2^{n ? 1} + n ? c(s) ? 2ⁿ ?1. A numerical study of the allowable values of c(s) for 3 ? n ? 6 found that all values in this range occurred except for 2^n?1 + n + 1. It is proven in this note that there are no de Bruijn sequences of complexity 2^n?1 + n + 1 for all n ? 3.     

Construction of doubly diagonalized orthogonal latin squares

A transversal T of a latin square is a collection of n cells no two in the same row or column and such that each of the integers 1, 2, …, n appears in exactly one of the cells of T. A latin square is doubly diagonalized provided that both its main diagonal and off-diagonal are transversals. Although it is known that a doubly diagonalized latin square of every order n ≥ 4 exists and that a pair of orthogonal latin squares of order n exists for every n ≠ 2 or 6, it is still an open question as to what the spectrum is for pairs of doubly diagonalized orthogonal latin squares. The best general result seems to be that pairs of orthogonal doubly diagonalized latin squares of order n exist whenever n is odd or a multiple of 4, except possibly when n is a multiple of 3 but not of 9. In this paper we give a new construction for doubly diagonalized latin squares which is used to enlarge the known class for doubly diagonalized orthogonal squares. The construction is based on Sade's singular direct product of quasigroups.     

Handcuffed designs

Handcuffed designs are a particular case of block designs on graphs. A handcuffed design with parameters v, k, λ consists of a system of ordered k-subsets of a v-set, called handcuffed blocks. In a block {A₁, A₂,…, A_k} each element is assumed to be handcuffed to its neighbors and the block contains k ? 1 handcuffed pairs (A₁, A₂), (A₂, A₁), …, (A_k?1, A_k). These pairs are considered unordered. The collection of handcuffed blocks constitutes a handcuffed design if the following are satisfied: (1) each element of the v-set appears amongst the blocks the same number of times (and at most once in a block) and (2) each pair of distinct elements of the v-set are handcuffed in exactly λ of the blocks. If the total number of blocks is b and each element appears in r blocks the following conditions are necessary for the handcuffed design to exist. (1) λv (v ? 1) = (k ? 1)b. (2) rv = kb. In this paper it is shown that the necessary conditions are also sufficient.     

On weighted lattice paths

A weighted lattice path from (1, 1) to (n, m) is a path consisting of unit vertical, horizontal, and diagonal steps of weight w. Let f(0), f(1), f(2), … be a nondecreasing sequence of positive integers; the path connecting the points of the set $\text{{(n, m) ¦ f(n ? 1) ? m ? f(n), n = 1, 2, …}}$ will be called the roof determined by f. We determine the number of weighted lattice paths from (1, 1) to (n + 1, f(n)) which do not cross the roof determined by f. We also determine the polynomials that must be placed in each cell below the roof such that if a 1 is placed in each cell whose lower left-hand corner is a point of the roof, every k × k square subarray comprised of adjacent rows and columns and containing at least one 1 will have determinant $\text{x(}\text{k}\text{2}\text{)}$.     

Regular graphs with high edge degree

For any vertex x of a graph G let Δ(x) denote the set of vertices adjacent to x. We seek to describe the connected graphs G which are regular of valence n and in which for all adjacent vertices x and y |Δ(x) ∩ Δ(y)| = n ? 1 ? s. It is known that the complete graphs are the graphs for which s = 0. For any s, any complete many-partite graph, each part containing s + 1 vertices, is such a graph. We show that these are the only such graphs for which the valence exceeds 2s² ? s + 1. The graphs satisfying these conditions for s = 1 or 2 are characterized (up to the class of trivalent triangle-free graphs.)     

On a variation of the Oberwolfach problem

We consider the following “spouse-avoiding” variant of the Oberwolfach problem (briefly NOP): “At a gathering there are n couples. Is it possible to arrange a seating for the 2n people present at s round tables T₁,T₂,…,T_s (where T_i can accomodate k_i ? 3 people and Σk_i=2n) for m different meals so that each person has every other person except his spouse for a neighbour exactly once?” We prove several results concerning the existence of solutions to NOP. In particular, we settle the cases when the tables accomodate the same “small” number of people or when there are only two tables one of them accomodating a “small” number of people or when the total number of people is “small”.