Design with mutually orthogonal resolutions

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