Difference between revisions of "Howell design"
(Importing text file) |
m (fix formatting) |
||
Line 3: | Line 3: | ||
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; | 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" />: | + | 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> | </td></tr> </table> | ||
Line 11: | Line 13: | ||
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" />. | 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]]]. | + | 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]]]). | 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]]]). |
Revision as of 18:58, 30 December 2015
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>
|
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 ![]() ![]() |
[a5] | D.R. Stinson, "The existence of Howell designs of odd side" J. Combin. Th. A , 32 (1982) pp. 53–65 |
Howell design. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Howell_design&oldid=14300