View source for Howell design

<!--
h1103301.png
$#A+1 = 78 n = 2
$#C+1 = 78 : ~/encyclopedia/old_files/data/H110/H.1100330 Howell design
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

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 ) $:

<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"> $  \alpha $
0</td> <td colname="2" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1">1 3</td> <td colname="4" style="background-color:white;" colspan="1"> $  \infty $
2</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">2 3</td> <td colname="2" style="background-color:white;" colspan="1"> $  \alpha $
1</td> <td colname="3" style="background-color:white;" colspan="1"> $  \infty $
0</td> <td colname="4" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"> $  \infty $
3</td> <td colname="3" style="background-color:white;" colspan="1"> $  \alpha $
2</td> <td colname="4" style="background-color:white;" colspan="1">0 1</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"></td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="2" style="background-color:white;" colspan="1"></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"> $  \infty $
1</td> <td colname="2" style="background-color:white;" colspan="1">0 2</td> <td colname="3" style="background-color:white;" colspan="1"></td> <td colname="4" style="background-color:white;" colspan="1"> $  \alpha $
3</td> </tr> </tbody> </table>

</td></tr> </table>

An  $  H ( 2n - 1,2n ) $
is also called a [[Room square|Room square]] of side  $  2n - 1 $. 
At the other extreme, the existence of a pair of mutually [[Orthogonal Latin squares|orthogonal Latin squares]] implies the existence of an  $  H ( n,2n ) $. 
The existence of Howell designs has been completely determined [[#References|[a1]]], [[#References|[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 ) $[[#References|[a1]]]. The existence of  $  H  ^ {*} ( s,2n ) $
for  $  s $
odd remains open, see [[#References|[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|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|one-factor]]. An  $  H ( n,2n ) $
with underlying graph  $  K _ {n,n }  $
is equivalent to a pair of mutually [[Orthogonal Latin squares|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 [[#References|[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 [[#References|[a3]]] [[#References|[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 [[#References|[a3]]], [[#References|[a2]]] for results on  $  \nu ( s,2n ) $
and existence results on  $  H _ {d} ( s,2n ) $.

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

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J.H. Dinitz,   "Howell designs"  C.J. Colbourn (ed.)  J.H. Dinitz (ed.) , ''CRC Handbook of Combinatorial Designs'' , CRC  (1996)  pp. 381–385</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  E.R. Lamken,   S.A. Vanstone,   "The existence of skew Howell designs of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033081.png" /> and order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033082.png" />"  ''J. Combin. Th. A'' , '''54'''  (1990)  pp. 20–40</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  D.R. Stinson,   "The existence of Howell designs of odd side"  ''J. Combin. Th. A'' , '''32'''  (1982)  pp. 53–65</TD></TR></table>