Room square

A Room square of side $ n $, $ { \mathop{\rm RS} } ( n ) $, is an $ ( n \times n ) $- array $ R $ defined on an $ ( n + 1 ) $- set $ V $ with the following properties:

1) each cell of $ R $ is either empty or contains an unordered pair of distinct elements from $ V $;

2) each element of $ V $ occurs precisely once in each row and column of $ R $;

3) every unordered pair of elements from $ V $ is in precisely one cell of $ R $. A necessary condition for a Room square of side $ n $ to exist is that $ n $ be odd. An example of a Room square of side $ 7 $ is listed below.

<tbody> </tbody> $ \infty $ 0 1 5 4 6 2 3 3 4 $ \infty $ 1 2 6 5 0 6 1 4 5 $ \infty $ 2 3 0 0 2 5 6 $ \infty $ 3 4 1 5 2 1 3 6 0 $ \infty $ 4 6 3 2 4 0 1 $ \infty $ 5 0 4 3 5 1 2 $ \infty $ 6

Room squares were named after T.G. Room, who published a paper in 1955 in which he constructed a Room square of side $ 7 $ and proved that Room squares of side $ 3 $ and $ 5 $ do not exist. However, Room squares were actually constructed much earlier. In 1850, T.M. Kirkman used a Room square of side $ 7 $ to solve the Kirkman schoolgirl problem for $ 15 $ girls, and the first infinite classes of Room squares were constructed by R.R. Anstice in 1852– 1853 [a1]. Several small Room squares were also constructed by E.C. Howell for use as schedules for duplicate bridge tournaments at the end of the nineteenth century. The existence of Room squares was finally completed in the early 1970s by R.C. Mullin and W.D. Wallis [a4]: A Room square of side $ n $ exists if and only if $ n $ is odd and $ n \neq 3 $ or $ 5 $. The proof uses a number of direct and recursive constructions. An extensive literature on Room squares is available, see [a3].

One application of Room squares is in the construction of round robin tournaments. A Room square of side $ n $ can be used to construct a round robin tournament with $ n + 1 $ teams which has the following properties: every team plays every other team exactly once during the tournament; every team plays in exactly one game in each round; and every team plays at every location exactly once.

A Room square of side $ n $ is standardized with respect to the element $ \infty $ if cell $ ( i,i ) $ contains the pair $ \{ \infty,i \} $. A standardized Room square of side $ n $ is skew if for every pair of cells $ ( i,j ) $ and $ ( j,i ) $( with $ i \neq j $) exactly one is filled. The existence of skew Room squares has been established [a5]: There exists a skew Room square of side $ n $ if and only if $ n $ is odd and $ n \neq 3 $ or $ 5 $. Skew Room squares have been quite useful in constructions for several other types of combinatorial designs, see [a3].

Room squares with additional properties have also been studied; these include Room squares with sub-Room squares (incomplete Room squares), maximum empty subarray Room squares, perfect Room squares, and balanced Room squares (complete balanced Howell rotations), see [a3] for references. For generalizations of Room squares to larger block size and higher dimension, see Design with mutually orthogonal resolutions.

Room squares are equivalent to several other combinatorial configurations, [a2]. In particular, the existence of the following designs are equivalent:

a) a Room square of side $ n $;

b) a Room frame of type $ 1 ^ {n} $;

c) two pairwise orthogonal symmetric Latin squares of order n (see Latin square);

d) a Howell design, $ H ( n,n + 1 ) $;

e) two pairwise orthogonal one-factorizations of $ K _ {n + 1 } $( cf. also One-factorization);

f) two orthogonal resolutions of an $ ( n + 1,2,1 ) $- BIBD (see Design with mutually orthogonal resolutions).

In some of the earlier literature, Room squares are also called Room designs.

References

[a1]	I. Anderson, "Cyclic designs in the 1850s; the work of Rev. R.R. Anstice" Bull. ICA , 15 (1995) pp. 41–46
[a2]	J.H. Dinitz, "Room squares" C.J. Colbourn (ed.) J.H. Dinitz (ed.) , CRC Handbook of Combinatorial Designs , CRC (1996) pp. 437–442
[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]	R.C. Mullin, W.D. Wallis, "The existence of Room squares" Aequat. Math. , 13 (1975) pp. 1–7
[a5]	D.R. Stinson, "The spectrum of skew Room squares" J. Austral. Math. Soc. A , 31 (1981) pp. 475–480