View source for Howell design

A Howell design of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h1103301.png" /> and order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h1103302.png" />, or more briefly an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h1103303.png" />, is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h1103304.png" />-array in which each cell is either empty or contains an unordered pair of distinct elements from some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h1103305.png" />-set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h1103306.png" /> such that:

1) every element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h1103307.png" /> occurs in precisely one cell of each row and each column;

2) every unordered pair of elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h1103308.png" /> is in at most one cell of the array. It follows immediately from the definition of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h1103309.png" /> that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033010.png" />. An example of a Howell design is the following <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033011.png" />:

<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"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033012.png" /> 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"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033013.png" /> 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"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033014.png" /> 1</td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033015.png" /> 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"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033016.png" /> 3</td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033017.png" /> 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"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033018.png" /> 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"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033019.png" /> 3</td> </tr> </tbody> </table>

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

An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033020.png" /> is also called a [[Room square|Room square]] of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033021.png" />. At the other extreme, the existence of a pair of mutually [[Orthogonal Latin squares|orthogonal Latin squares]] implies the existence of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033022.png" />. The existence of Howell designs has been completely determined [[#References|[a1]]], [[#References|[a5]]]: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033024.png" /> be positive integers such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033025.png" />. There exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033026.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033027.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033028.png" />. The proof uses a variety of direct and recursive constructions.

An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033029.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033030.png" /> in which there is a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033031.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033032.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033033.png" />, such that no pair of elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033034.png" /> appears in the design. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033036.png" />-designs are quite useful in recursive constructions. There exist <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033037.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033038.png" /> even, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033039.png" />, with two exceptions: there is no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033040.png" /> and there is no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033041.png" /> [[#References|[a1]]]. The existence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033042.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033043.png" /> odd remains open, see [[#References|[a5]]]. The only known case where an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033044.png" /> exists but an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033045.png" /> does not is for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033046.png" />.

The pairs of elements in the cells of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033047.png" /> can be thought of as the edges of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033048.png" />-regular [[Graph|graph]] on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033049.png" />-set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033050.png" />, the underlying graph of the Howell design. The existence of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033051.png" /> is equivalent to the existence of a pair of orthogonal one-factorizations of the underlying graph of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033052.png" /> (cf. [[One-factorization|One-factorization]]). The underlying graph of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033053.png" /> is the complete graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033054.png" />, and the underlying graph of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033055.png" /> is the [[cocktail party graph]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033056.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033057.png" /> is a [[One-factor|one-factor]]. An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033058.png" /> with underlying graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033059.png" /> is equivalent to a pair of mutually [[Orthogonal Latin squares|orthogonal Latin squares]] of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033060.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033061.png" />-designs, skew designs, complementary designs, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033062.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033064.png" />-dimensional Howell design, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033065.png" />, is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033066.png" />-dimensional array in which every cell either is empty or contains an unordered pair of elements from a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033067.png" />-set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033068.png" /> and such that each two-dimensional projection is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033069.png" />. An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033070.png" /> is called a Howell cube. An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033071.png" /> is equivalent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033072.png" /> mutually orthogonal one-factorizations of the underlying graph. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033073.png" /> denote the maximum value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033074.png" /> such that an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033075.png" /> exists. Very little is known about upper bounds for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033076.png" />. It is easy to see that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033077.png" />, and it has been conjectured that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033078.png" />. See [[#References|[a3]]], [[#References|[a2]]] for results on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033079.png" /> and existence results on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110330/h11033080.png" />.

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>