Howell design

A Howell design of side $s$ and order $2n$, or more briefly an $H ( s,2n )$, is an $( s \times s )$- array in which each cell is either empty or contains an unordered pair of distinct elements from some $2n$- set $V$ such that:

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

2) every unordered pair of elements from $V$ is in at most one cell of the array. It follows immediately from the definition of an $H ( s,2n )$ that $n \leq s \leq 2n - 1$. An example of a Howell design is the following $H ( 4,6 )$:

<tbody> </tbody> $\alpha$ 0 1 3 $\infty$ 2 2 3 $\alpha$ 1 $\infty$ 0 $\infty$ 3 $\alpha$ 2 0 1 $\infty$ 1 0 2 $\alpha$ 3

An $H ( 2n - 1,2n )$ is also called a Room square of side $2n - 1$. At the other extreme, the existence of a pair of mutually orthogonal Latin squares implies the existence of an $H ( n,2n )$. The existence of Howell designs has been completely determined [a1], [a5]: Let $s$ and $n$ be positive integers such that $0 \leq n \leq s \leq 2n - 1$. There exists an $H ( s,2n )$ if and only if $( s,2n ) \neq ( 2,4 ) , ( 3,4 ) , ( 5,6 )$ or $( 5,8 )$. The proof uses a variety of direct and recursive constructions.

An $H ^ {*} ( s,2n )$ is an $H ( s,2n )$ in which there is a subset $W$ of $V$, $| W | = 2n - s$, such that no pair of elements from $W$ appears in the design. $*$- designs are quite useful in recursive constructions. There exist $H ^ {*} ( s,2n )$ for $s$ even, $n \leq s \leq 2n - 2$, with two exceptions: there is no $H ^ {*} ( 2,4 )$ and there is no $H ^ {*} ( 6,12 )$[a1]. The existence of $H ^ {*} ( s,2n )$ for $s$ odd remains open, see [a5]. The only known case where an $H ( s,2n )$ exists but an $H ^ {*} ( s,2n )$ does not is for $s = n = 6$.

The pairs of elements in the cells of an $H ( s,2n )$ can be thought of as the edges of an $s$- regular graph on the $2n$- set $V$, the underlying graph of the Howell design. The existence of an $H ( s,2n )$ is equivalent to the existence of a pair of orthogonal one-factorizations of the underlying graph of the $H ( s,2n )$( cf. One-factorization). The underlying graph of an $H ( 2n - 1,2n )$ is the complete graph $K _ {2n }$, and the underlying graph of an $H ( 2n - 2,2n )$ is the cocktail party graph $K _ {2n } - f$, where $f$ is a one-factor. An $H ( n,2n )$ with underlying graph $K _ {n,n }$ is equivalent to a pair of mutually orthogonal Latin squares of order $n$. 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 $d$- dimensional Howell design, $H _ {d} ( s,2n )$, is a $d$- dimensional array in which every cell either is empty or contains an unordered pair of elements from a $2n$- set $V$ and such that each two-dimensional projection is an $H ( s,2n )$. An $H _ {3} ( s,2n )$ is called a Howell cube. An $H _ {d} ( s,2n )$ is equivalent to $d$ mutually orthogonal one-factorizations of the underlying graph. Let $\nu ( s,2n )$ denote the maximum value of $d$ such that an $H _ {d} ( s,2n )$ exists. Very little is known about upper bounds for $\nu ( s,2n )$. It is easy to see that $\nu ( s,2n ) \leq s - 1$, and it has been conjectured that $\nu ( s,2n ) \leq n - 1$. See [a3], [a2] for results on $\nu ( s,2n )$ and existence results on $H _ {d} ( s,2n )$.

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