Howell design

A Howell design of side and order , or more briefly an , is an -array in which each cell is either empty or contains an unordered pair of distinct elements from some -set such that:

1) every element of occurs in precisely one cell of each row and each column;

2) every unordered pair of elements from is in at most one cell of the array. It follows immediately from the definition of an that . An example of a Howell design is the following :

<tbody> </tbody> 0 1 3 2 2 3 1 0 3 2 0 1 1 0 2 3

An is also called a Room square of side . At the other extreme, the existence of a pair of mutually orthogonal Latin squares implies the existence of an . The existence of Howell designs has been completely determined [a1], [a5]: Let and be positive integers such that . There exists an if and only if or . The proof uses a variety of direct and recursive constructions.

An is an in which there is a subset of , , such that no pair of elements from appears in the design. -designs are quite useful in recursive constructions. There exist for even, , with two exceptions: there is no and there is no [a1]. The existence of for odd remains open, see [a5]. The only known case where an exists but an does not is for .

The pairs of elements in the cells of an can be thought of as the edges of an -regular graph on the -set , the underlying graph of the Howell design. The existence of an is equivalent to the existence of a pair of orthogonal one-factorizations of the underlying graph of the (cf. One-factorization). The underlying graph of an is the complete graph , and the underlying graph of an is the cocktail party graph , where is a one-factor. An with underlying graph is equivalent to a pair of mutually orthogonal Latin squares of order . The general problem of determining which graphs are the underlying graphs of a Howell design remains open (1996), see [a3].

Several special types of Howell designs have been studied, including -designs, skew designs, complementary designs, -complementary designs, cyclic Howell designs (used for Howell movements in duplicate bridge), and Howell designs with Howell sub-designs (see [a3] [a4]).

A -dimensional Howell design, , is a -dimensional array in which every cell either is empty or contains an unordered pair of elements from a -set and such that each two-dimensional projection is an . An is called a Howell cube. An is equivalent to mutually orthogonal one-factorizations of the underlying graph. Let denote the maximum value of such that an exists. Very little is known about upper bounds for . It is easy to see that , and it has been conjectured that . See [a3], [a2] for results on and existence results on .

The survey article [a3] includes results and references on Howell designs.

References

[a1]	B.A. Anderson, P.J. Schellenberg, D.R. Stinson, "The existence of Howell designs of even side" J. Combin. Th. A , 36 (1984) pp. 23–55
[a2]	J.H. Dinitz, "Howell designs" C.J. Colbourn (ed.) J.H. Dinitz (ed.) , CRC Handbook of Combinatorial Designs , CRC (1996) pp. 381–385
[a3]	J.H. Dinitz, D.R. Stinson, "Room squares and related designs" J.H. Dinitz (ed.) D.R. Stinson (ed.) , Contemporary Design Theory: A Collection of Surveys , Wiley (1992) pp. 137–204
[a4]	E.R. Lamken, S.A. Vanstone, "The existence of skew Howell designs of side and order " J. Combin. Th. A , 54 (1990) pp. 20–40
[a5]	D.R. Stinson, "The existence of Howell designs of odd side" J. Combin. Th. A , 32 (1982) pp. 53–65