Namespaces
Variants
Actions

Difference between revisions of "Design with mutually orthogonal resolutions"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Tex partly done)
(Tex done)
 
Line 3: Line 3:
 
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)$.
 
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 $d$, where $d$ is the size of the largest set of mutually orthogonal resolutions for a design. The case for Room cubes has received considerable attention. Let $\nu(n)$ denote the maximum $d$ for which there exists a Room $d$-cube of side $n$. A simple counting argument gives $\nu(n) \le n-2$. However, evidence from small designs and constructions supports a conjecture (from 1973) that $\nu(n) \le (n-1)/2$. This conjecture and a good upper bound for $\nu(n)$ remain open problems (1996), [[#References|[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 [[#References|[a3]]] for references. Results on Room <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016055.png" />-cubes can also be found in [[#References|[a3]]]. Results for balanced incomplete block designs with block size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016056.png" /> can be found in [[#References|[a2]]], [[#References|[a4]]], [[#References|[a6]]], and existence results and bounds for other types of designs can be found in [[#References|[a7]]].
+
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 [[#References|[a3]]] for references. Results on Room $d$-cubes can also be found in [[#References|[a3]]]. Results for balanced incomplete block designs with block size $k\ge3$ can be found in [[#References|[a2]]], [[#References|[a4]]], [[#References|[a6]]], and existence results and bounds for other types of designs can be found in [[#References|[a7]]].
  
Partial resolutions can also be used in place of resolutions in the definitions above. Examples of such designs include <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110160/d11016057.png" />-BIBDs with mutually orthogonal near resolutions (see [[#References|[a5]]]) and frames which use group divisible designs (see [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]]).
+
Partial resolutions can also be used in place of resolutions in the definitions above. Examples of such designs include $(v,k,k-1)$-BIBDs with mutually orthogonal near resolutions (see [[#References|[a5]]]) and frames which use group divisible designs (see [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]]).
  
 
For recent results on resolvable designs, see [[#References|[a1]]].
 
For recent results on resolvable designs, see [[#References|[a1]]].
Line 14: Line 14:
  
 
====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 $(v,3,2)$-BIBDs"  ''J. Combin. Th. A'' , '''72'''  (1995)  pp. 50–76 {{ZBL|0836.05008}}</TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top">  E.R. Lamken,  "The existence of doubly near resolvable $(v,3,2)$-BIBDs"  ''J. Combin. Designs'' , '''2'''  (1994)  pp. 427–440 {{ZBL|0822.05003}}</TD></TR>
 +
<TR><TD valign="top">[a6]</TD> <TD valign="top">  E.R. Lamken,  "Constructions for resolvable and near resolvable $(v,k,k-1)$-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}}
+
{{TEX|done}}

Latest revision as of 15:08, 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 $d$, where $d$ is the size of the largest set of mutually orthogonal resolutions for a design. The case for Room cubes has received considerable attention. Let $\nu(n)$ denote the maximum $d$ for which there exists a Room $d$-cube of side $n$. A simple counting argument gives $\nu(n) \le n-2$. However, evidence from small designs and constructions supports a conjecture (from 1973) that $\nu(n) \le (n-1)/2$. This conjecture and a good upper bound for $\nu(n)$ 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 $d$-cubes can also be found in [a3]. Results for balanced incomplete block designs with block size $k\ge3$ 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 $(v,k,k-1)$-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 $(v,3,2)$-BIBDs" J. Combin. Th. A , 72 (1995) pp. 50–76 Zbl 0836.05008
[a5] E.R. Lamken, "The existence of doubly near resolvable $(v,3,2)$-BIBDs" J. Combin. Designs , 2 (1994) pp. 427–440 Zbl 0822.05003
[a6] E.R. Lamken, "Constructions for resolvable and near resolvable $(v,k,k-1)$-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=42967
This article was adapted from an original article by E.R. Lamken (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article