Namespaces
Variants
Actions

Difference between revisions of "Design with mutually orthogonal resolutions"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(Tex partly done)
Line 1: Line 1:
A combinatorial design <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d1101601.png" /> (cf. also [[Block design|Block design]]) with replication number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d1101602.png" /> is said to be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d1101604.png" />-resolvable if the blocks of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d1101605.png" /> can be partitioned into classes (called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d1101607.png" />-resolution classes) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d1101608.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d1101609.png" />) such that each element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016010.png" /> is contained in precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016011.png" /> blocks of each class. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016012.png" />, the design is called resolvable. Two <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016013.png" />-resolutions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016015.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016016.png" /> are called orthogonal if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016017.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016018.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016019.png" />. (It should be noted that the blocks of the design are considered as being labeled so that if a subset of the element set occurs as a block more than once, the blocks are treated as being distinct.) A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016020.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016021.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016022.png" />-resolutions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016023.png" /> is called a set of mutually orthogonal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016025.png" />-resolutions if the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016026.png" />-resolutions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016027.png" /> are pairwise orthogonal. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016028.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016029.png" /> is a set of mutually orthogonal resolutions. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016030.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016031.png" />, the design is called doubly resolvable.
+
A combinatorial design $D$ (cf. also [[Block design]]) with replication number $r$ is said to be $\mu$-resolvable if the blocks of $D$ can be partitioned into classes (called $\mu$-resolution classes) $R_1,\ldots,R_t$ (where $t=r/\mu$) such that each element of $D$ is contained in precisely $\mu$ blocks of each class. If $\mu=1$, the design is called ''resolvable''. Two $\mu$-resolutions $R$ and $R'$ of $D$ are called ''orthogonal'' if $|R_i \cap R_j'| \le 1$ for all $R_i \in R$, $R_j' \in R'$. (It should be noted that the blocks of the design are considered as being labeled so that if a subset of the element set occurs as a block more than once, the blocks are treated as being distinct.) A set $Q = \{R^1,\ldots,R^d\}$ of $d$ $\mu$-resolutions of $D$ is called a set of mutually orthogonal $\mu$-resolutions if the $\mu$-resolutions of $Q$ are pairwise orthogonal. If $\mu=1$, then $Q$ is a set of mutually orthogonal resolutions. If $d=2$ and $\mu=1$, the design is called doubly resolvable.
  
The existence of a [[Room square|Room square]] of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016032.png" /> is equivalent to the existence of a doubly resolvable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016033.png" />-BIBD (cf. also [[Block design|Block design]]). The rows form one resolution and the columns form an orthogonal resolution. A Room <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016035.png" />-cube of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016036.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016037.png" />-dimensional array, each cell of which either is empty or contains an unordered pair of elements, such that each two-dimensional projection is a Room square of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016038.png" />. The existence of a Room <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016039.png" />-cube of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016040.png" /> is equivalent to the existence of a set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016041.png" /> mutually orthogonal resolutions of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016042.png" />-BIBD. A pair of orthogonal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016043.png" />-resolutions of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016044.png" />-BIBD can also be used to construct an array, a Kirkman square <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016045.png" />.
+
The existence of a [[Room square]] of side $n$ is equivalent to the existence of a doubly resolvable $(n+1,2,1)$-BIBD (cf. also [[Block design]]). The rows form one resolution and the columns form an orthogonal resolution. A Room $d$-cube of side $n$ is a $d$-dimensional array, each cell of which either is empty or contains an unordered pair of elements, such that each two-dimensional projection is a Room square of side $n$. The existence of a Room $d$-cube of side $n$ is equivalent to the existence of a set of $d$ mutually orthogonal resolutions of an $(n+1,2,1)$-BIBD. A pair of orthogonal $\mu$-resolutions of a $(v,k,\lambda)$-BIBD can also be used to construct an array, a Kirkman square $\mathrm{KS}_k(v;\mu,\lambda)$.
  
 
An important open question in design theory is determining a good upper bound for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016046.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016047.png" /> is the size of the largest set of mutually orthogonal resolutions for a design. The case for Room cubes has received considerable attention. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016048.png" /> denote the maximum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016049.png" /> for which there exists a Room <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016050.png" />-cube of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016051.png" />. A simple counting argument gives <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016052.png" />. However, evidence from small designs and constructions supports a conjecture (from 1973) that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016053.png" />. This conjecture and a good upper bound for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016054.png" /> remain open problems (1996), [[#References|[a3]]].
 
An important open question in design theory is determining a good upper bound for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016046.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016047.png" /> is the size of the largest set of mutually orthogonal resolutions for a design. The case for Room cubes has received considerable attention. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016048.png" /> denote the maximum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016049.png" /> for which there exists a Room <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016050.png" />-cube of side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016051.png" />. A simple counting argument gives <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016052.png" />. However, evidence from small designs and constructions supports a conjecture (from 1973) that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016053.png" />. This conjecture and a good upper bound for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016054.png" /> remain open problems (1996), [[#References|[a3]]].
Line 15: Line 15:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.J.R. Abel,  S.C. Furino,  "Resolvable and near resolvable designs"  C.J. Colbourn (ed.)  J.H. Dinitz (ed.) , ''CRC Handbook of Combinatorial Designs'' , CRC  (1996)  pp. 87–94</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  C.J. Colbourn,  A. Rosa,  "Orthogonal resolutions of triple systems"  ''Australasian J. Combin.'' , '''12'''  (1995)  pp. 259–269</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,  "The existence of doubly resolvable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016058.png" />-BIBDs"  ''J. Combin. Th. A'' , '''72'''  (1995)  pp. 50–76</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  E.R. Lamken,  "The existence of doubly near resolvable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016059.png" />-BIBDs"  ''J. Combin. Designs'' , '''2'''  (1994)  pp. 427–440</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  E.R. Lamken,  "Constructions for resolvable and near resolvable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016060.png" />-BIBDs"  D.K. Ray-Chaudhuri (ed.) , ''Coding Theory and Design Theory. Part II. Design Theory'' , Springer  (1990)  pp. 236–250</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  E.R. Lamken,  S.A. Vanstone,  "Designs with mutually orthogonal resolutions"  ''European J. Combin.'' , '''7'''  (1986)  pp. 249–257</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.J.R. Abel,  S.C. Furino,  "Resolvable and near resolvable designs"  C.J. Colbourn (ed.)  J.H. Dinitz (ed.) , ''CRC Handbook of Combinatorial Designs'' , CRC  (1996)  pp. 87–94</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  C.J. Colbourn,  A. Rosa,  "Orthogonal resolutions of triple systems"  ''Australasian J. Combin.'' , '''12'''  (1995)  pp. 259–269</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,  "The existence of doubly resolvable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016058.png" />-BIBDs"  ''J. Combin. Th. A'' , '''72'''  (1995)  pp. 50–76</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  E.R. Lamken,  "The existence of doubly near resolvable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016059.png" />-BIBDs"  ''J. Combin. Designs'' , '''2'''  (1994)  pp. 427–440</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  E.R. Lamken,  "Constructions for resolvable and near resolvable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016060.png" />-BIBDs"  D.K. Ray-Chaudhuri (ed.) , ''Coding Theory and Design Theory. Part II. Design Theory'' , Springer  (1990)  pp. 236–250</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  E.R. Lamken,  S.A. Vanstone,  "Designs with mutually orthogonal resolutions"  ''European J. Combin.'' , '''7'''  (1986)  pp. 249–257</TD></TR></table>
 +
 +
{{TEX|part}}

Revision as of 12:48, 19 March 2018

A combinatorial design $D$ (cf. also Block design) with replication number $r$ is said to be $\mu$-resolvable if the blocks of $D$ can be partitioned into classes (called $\mu$-resolution classes) $R_1,\ldots,R_t$ (where $t=r/\mu$) such that each element of $D$ is contained in precisely $\mu$ blocks of each class. If $\mu=1$, the design is called resolvable. Two $\mu$-resolutions $R$ and $R'$ of $D$ are called orthogonal if $|R_i \cap R_j'| \le 1$ for all $R_i \in R$, $R_j' \in R'$. (It should be noted that the blocks of the design are considered as being labeled so that if a subset of the element set occurs as a block more than once, the blocks are treated as being distinct.) A set $Q = \{R^1,\ldots,R^d\}$ of $d$ $\mu$-resolutions of $D$ is called a set of mutually orthogonal $\mu$-resolutions if the $\mu$-resolutions of $Q$ are pairwise orthogonal. If $\mu=1$, then $Q$ is a set of mutually orthogonal resolutions. If $d=2$ and $\mu=1$, the design is called doubly resolvable.

The existence of a Room square of side $n$ is equivalent to the existence of a doubly resolvable $(n+1,2,1)$-BIBD (cf. also Block design). The rows form one resolution and the columns form an orthogonal resolution. A Room $d$-cube of side $n$ is a $d$-dimensional array, each cell of which either is empty or contains an unordered pair of elements, such that each two-dimensional projection is a Room square of side $n$. The existence of a Room $d$-cube of side $n$ is equivalent to the existence of a set of $d$ mutually orthogonal resolutions of an $(n+1,2,1)$-BIBD. A pair of orthogonal $\mu$-resolutions of a $(v,k,\lambda)$-BIBD can also be used to construct an array, a Kirkman square $\mathrm{KS}_k(v;\mu,\lambda)$.

An important open question in design theory is determining a good upper bound for , where is the size of the largest set of mutually orthogonal resolutions for a design. The case for Room cubes has received considerable attention. Let denote the maximum for which there exists a Room -cube of side . A simple counting argument gives . However, evidence from small designs and constructions supports a conjecture (from 1973) that . This conjecture and a good upper bound for remain open problems (1996), [a3].

In general, very little is known about the existence of designs with mutually orthogonal resolutions. Necessary and sufficient conditions are known for the existence of Kirkman squares with block size two and for Room squares; see [a3] for references. Results on Room -cubes can also be found in [a3]. Results for balanced incomplete block designs with block size can be found in [a2], [a4], [a6], and existence results and bounds for other types of designs can be found in [a7].

Partial resolutions can also be used in place of resolutions in the definitions above. Examples of such designs include -BIBDs with mutually orthogonal near resolutions (see [a5]) and frames which use group divisible designs (see [a3], [a4], [a5]).

For recent results on resolvable designs, see [a1].

The terminology has not yet been standardized for the arrays constructed from designs with mutually orthogonal resolutions. Generalized Room squares, Kirkman cubes, and multi-dimensional Kirkman arrays all refer to designs with mutually orthogonal resolutions.

References

[a1] R.J.R. Abel, S.C. Furino, "Resolvable and near resolvable designs" C.J. Colbourn (ed.) J.H. Dinitz (ed.) , CRC Handbook of Combinatorial Designs , CRC (1996) pp. 87–94
[a2] C.J. Colbourn, A. Rosa, "Orthogonal resolutions of triple systems" Australasian J. Combin. , 12 (1995) pp. 259–269
[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, "The existence of doubly resolvable -BIBDs" J. Combin. Th. A , 72 (1995) pp. 50–76
[a5] E.R. Lamken, "The existence of doubly near resolvable -BIBDs" J. Combin. Designs , 2 (1994) pp. 427–440
[a6] E.R. Lamken, "Constructions for resolvable and near resolvable -BIBDs" D.K. Ray-Chaudhuri (ed.) , Coding Theory and Design Theory. Part II. Design Theory , Springer (1990) pp. 236–250
[a7] E.R. Lamken, S.A. Vanstone, "Designs with mutually orthogonal resolutions" European J. Combin. , 7 (1986) pp. 249–257
How to Cite This Entry:
Design with mutually orthogonal resolutions. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Design_with_mutually_orthogonal_resolutions&oldid=42965
This article was adapted from an original article by E.R. Lamken (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article