\documentstyle [12pt] {article}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 1 (1994), \#R7\hfill}
\thispagestyle{empty}
\setlength{\textwidth}{6.0in}
\setlength{\textheight}{9.0in}
\addtolength{\oddsidemargin}{-0.5in}
\addtolength{\topmargin}{-1.0in}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{defn}{Definition}[section]
\newtheorem{con}{Construction}[section]

 \def\whitebox{{\hbox{\hskip 1pt
	  \vrule height 6pt depth 1.5pt
\lower 1.5pt\vbox to 7.5pt{\hrule width
3.2pt\vfill\hrule width 3.2pt}%
\vrule height 6pt depth 1.5pt
\hskip 1pt } }}
\def\qed{\ifhmode\allowbreak\else\nobreak\fi\hfill\quad\nobreak
        \whitebox\medbreak}

\begin{document}
\title{On the Spectra of Certain Classes of Room Frames}
\author{Jeffrey H.\ Dinitz \\
Department of Mathematics\\
University of Vermont\\ 
Burlington, Vermont 05405, USA \vspace{.25in}\\
Douglas R.\ Stinson \\
Computer Science and Engineering Department\\ and 
Center for Communication and Information Science\\
University of Nebraska-Lincoln\\ 
Lincoln, Nebraska 68588, USA \vspace{.25in}\\
L.\ Zhu \\
Department of Mathematics\\ 
Suzhou University, Suzhou 215006\\ 
People's Republic of China }
\date{Submitted: June 14, 1994; Accepted: September 14, 1994.}
\maketitle



\begin{abstract}
In this paper we study the spectra of certain classes of Room frames.
The three spectra are 
incomplete Room squares, uniform Room frames
and Room frames of type $2^ut^1$.  These problems have been studied in numerous
papers over the years; in this paper, we complete the three spectra except
for one possible exception in each case.

\vspace{.1in}
\noindent  Math reviews classification: 05B15
\end{abstract}

\section{Introduction}
\label{s1}
Room squares and generalizations have been extensively studied for
over 35 years.  In 1974, Mullin and Wallis \cite{M25} showed that the spectrum 
of Room squares
consists of all odd positive integers other than 3 or 5; however, 
many other related questions have
remained unsolved.  (For a recent survey, see \cite{DS92}.)
In this paper, we study three well-known spectra: 
\begin{description}
\item [Incomplete Room squares]  This problem asks for which ordered pairs 
$(n,s)$ does there exist a Room square of 
side $n$ containing a Room square of side $s$ as a subarray.
By considering ``incomplete'' Room squares, we can allow $s= 3$ or $5$, as
well.
This problem has been under investigation for over 20 years, and a
history up to 1992 can be found in \cite{DS92}.  Two more recent papers are
\cite{SZ93,DZ93}.
\item [Uniform Room frames]  This problem involves the determination
of the existence of Room frames of type $t^u$ 
(i.e.\ having $u$ holes of size $t$).  A systematic study of this problem was
begun in 1981 in \cite{D13}.  The history up to 1992 is found in \cite{DS92}
and more recent results appear in \cite{GZ93,DL93}.
\item [Room frames of type $2^ut^1$]  Here we are asking for Room frames 
with one hole of size $t$ and $u$ holes of size 2.  This problem can be thought
of as an even-side analogue of the incomplete Room square problem.
The known results on this problem can be found in \cite{G99,GZ99}.
\end{description}

We will describe our new results more precisely a bit later in this 
introduction, but we first give some formal definitions.
We first define a very general object we call a holey Room square.  
Let $S$ be a set, let $\infty $ be a ``special'' symbol not in $S$, 
and let $\cal H$ be a set of subsets of $S$.  A {\it holey Room square} 
having {\it hole set} $\cal H$ is an $|S| \times |S|$ array, $F$, 
indexed by $S$, which satisfies the following properties:

\begin{enumerate}
\item Every cell of $F$ either is empty or contains an unordered 
pair of symbols of $S \bigcup \{ \infty \} $.
\item Every symbol of $S \bigcup \{ \infty \} $ occurs at most 
once in any row or column of $F$, and every unordered pair of 
symbols occurs in at most one cell of $F$.
\item The subarrays $H \times H$ are empty, for every $H \in {\cal H}$ 
(these subarrays are referred to as {\it holes}).
\item The symbol $s \in S$ occurs in row or column $t$ if and only if 
\[(s, t) \in (S \times S) \backslash 
\bigcup_{H \in {\cal H}}^{} (H \times H);\] 
and symbol $\infty $ occurs in row or column $t$ if and only if 
\[t \in S \backslash \bigcup_{H \in {\cal H}}^{} {H}.\]
\item The pair $\{ s, t\} $ occurs in $F$ if and only if 
\[(s, t) \in (S \times S) \backslash 
\bigcup_{H \in {\cal H}}^{} (H \times H);\] 
the pair $\{ \infty , t\} $ occurs in $F$ if and only if 
\[t \in S \backslash \bigcup_{H \in {\cal H}}^{} {H}.\]
\end{enumerate}
The holey Room square $F$ will be denoted as HRS$({\cal H})$.  
The {\it order} of $F$ is $|S|$.  Note that $\infty$ does not occur 
in {\it any} cell of $F$ if $\bigcup_{H \in {\cal H}}^{} {H} = S$.  

We now identify several special cases of holey 
Room squares.  
First, if ${\cal H} = \emptyset $, then an HRS$({\cal H})$ is just a 
{\it Room square} of {\it side} $|S|$.  
Also, if ${\cal H} = \{ H\} $, then an HRS$({\cal H})$ is an 
$(|S|,|H|)-${\it incomplete Room square}, or $(|S|,|H|)-$IRS. 

If ${\cal H} = \{ S_1, \dots , S_n\}$ is a partition of $S$, 
then an HRS$({\cal H})$ is called a {\it Room frame}.  As is 
usually done in the literature, we refer to a Room frame simply 
as a {\it frame}.  The {\it type} of the frame is defined to be 
the multiset $\{ |S_i|: 1 \leq i \leq n\} $.  We usually use an 
``exponential'' notation to describe types:  a type 
${t_1}^{u_1}{t_2}^{u_2} \dots {t_k}^{u_k}$ denotes $u_i$ occurrences of 
$t_i$, $1 \leq i \leq k$. 

We do not display any specific Room frames in this paper, but examples
are shown in numerous papers, such as \cite{DS92} and \cite{DS93}.

We observe that existence of a Room square of side $n$ is equivalent 
to existence of a frame of type $1^n$; and existence of an $(n, s)-$IRS 
is equivalent to existence of a frame of type $1^{n-s}s^1$.

If ${\cal H} = \{ S_1, \dots , S_n, T\}$ , where $\{ S_1, \dots , S_n\}$ 
is a partition of $S$, then an HRS$({\cal H})$ is called an 
{\it incomplete frame} or an {\it I$-$frame}.  The 
{\it type} of the I$-$frame is defined to be the multiset 
$\{ (|S_i|, |S_i \bigcap T|): 1 \leq i \leq n\} $.  
We may also use an ``exponential'' notation to describe types of I$-$frames. 

%definition of double frame here

We also make use of a new type of HRS.
Suppose ${\cal H} = \{ S_1, \dots , S_n,  T_1, \dots , T_m\}$,
where $\{ S_1, \dots , S_n\}$ and  
$\{T_1, \dots , T_m\}$
are both partitions of $S$.
Then an HRS$({\cal H})$ is called a {\it double frame}.
For $1\leq i \leq n$, $1 \leq j \leq m$, define $a_{ij} = | S_i \cap T_j|$.
Then the {\it type} of the double frame HRS$({\cal H})$ is defined to
be the $n \times m$ matrix $A = (a_{ij})$.

It is immediate that $n$ must be odd for a Room square of side $n$ to exist.  
The spectrum of Room squares was determined in 1974 by Mullin and Wallis 
\cite{M25}.

\begin{thm}
\cite{M25}
\label{t1.1}
A Room square of side $n$ exists if and only if $n$ is odd and $n \neq 3$ or 5.
\end{thm}

A frame of type $t^u$ is called {\it uniform}.  Uniform frames have been studied
by several researchers.  
The following theorem summarizes known existence results.

\begin{thm}
\label{uf}
\cite{D13,GZ93,DL93}
Suppose $t$ and $u$ are positive integers, $u\geq 4$, and 
$(t,u) \neq (1,5), (2,4)$. 
Then there exists a frame of type $t^u$ if and only if $t(u-1)$ is even, 
except possibly when $u =4$ and $t = 14$, $22$, $26$, $34$, $38$, $46$, $62$,
$74$, $82$, $86$, $98$, $122$, $134$, $146$.
\end{thm}

Many papers over the years have studied constructions for IRS.
It is not difficult to see that, if $s \neq 0$, then existence of 
an $(n,s)-$IRS requires that $n$ and $s$ be odd and 
$n \geq 3s + 2$.  The Existence Conjecture \cite{S23} is 
that these conditions are sufficient for existence of an $(n,s)-$IRS, 
with the single exception $(n,s) \neq (5,1)$.  In fact, 
the Existence Conjecture has been proved with only 45 possible exceptions
remaining unknown.
The following theorem summarizes the current situation.

\begin{thm}
\cite{SZ93,DZ93}
\label{t1.2}
Suppose $n$ and $s$ are odd positive integers, $n \geq 3s+2$, and 
$(n,s) \neq (5,1)$. Then there exists an $(n,s)-$IRS except possibly for the
following 45 ordered pairs:
\begin{center}
\begin{tabular}{llllllll}
$(55,17)$ &  $(59,17)$ &  $(61,17)$ &  $(63,17)$ &  $(61,19)$ &  $(63,19)$ &  
$(65,19)$ \\  
$(67,21)$ &  
$(79,25)$ &  $(81,25)$ &  $(83,25)$ &  $(85,27)$ &  $(89,27)$ &  $(93,27)$ \\  
$(95,27)$ &  $(91,29)$ & 
$(95,29)$ &  $(97,29)$ &  $(97,31)$ &  $(99,31)$ &  $(109,35)$ \\  
$(111,35)$ &  $(115,37)$ &  $(127,41)$ & 
$(129,41)$ &  $(139,45)$ &  $(143,45)$ &  $(145,47)$ \\  
$(149,47)$ &  
$(151,47)$ &  $(153,47)$ &  $(151,49)$ & 
$(153,49)$ &  $(157,51)$ &  $(169,55)$ \\  
$(171,55)$ &  $(173,55)$ &  
$(175,57)$ &  $(271,89)$ &  $(275,89)$ &
$(277,89)$ &  $(319,105)$ \\  
$(325,105)$ &  $(327,105)$ &  $(367,121)$.
\end{tabular}
\end{center}
\end{thm}

We mentioned above that an $(n,s)-$IRS is equivalent to a frame of type
$1^{n-s}s^1$.  The order of such a frame is odd.  If we wanted to study
an even order analogue of these frames, the most natural types to consider
would be types $2^ut^1$.  Frames of these types were studied in \cite{G99,GZ99},
where the following results were proved.

\begin{thm}
\label{old2ut1}
\cite{G99,GZ99}
Suppose $t$ and $u$ are positive integers.
If $t \geq 20$ or $t=4$, then
there exists a frame of type $2^ut^1$ if and only if $t$ is even
and $u \geq t+1$.
Also, for $6 \leq t \leq 18$, there exists a frame of type $2^ut^1$ 
if $t$ is even
and $u \geq 5 \left\lceil {t \over 4} \right\rceil + 20$.
\end{thm}

We now describe the main results of this paper. 
For uniform Room frames, we have removed all but one of the possible exceptions,
so we have the following:

\begin{thm}
\label{newuf}
Suppose $t$ and $u$ are positive integers, $u\geq 4$, and 
$(t,u) \neq (1,5), (2,4)$. 
Then there exists a frame of type $t^u$ if and only if $t(u-1)$ is even, 
except possibly when $u =4$ and $t = 14$.
\end{thm}

We construct IRS for
44 of the 45 exceptions given in Theorem \ref{t1.2}, so the following
theorem results:

\begin{thm}
\label{newirs}
Suppose $n$ and $s$ are odd positive integers, $n \geq 3s+2$, and 
$(n,s) \neq (5,1)$. Then there exists an $(n,s)-$IRS, except possibly 
for $(n,s) = (67,21)$.
\end{thm}

For Room frames of type $2^ut^1$, we can also eliminate all but one of the 
possible exceptions, producing the following theorem:

\begin{thm}
Suppose $t$ and $u$ are positive integers.
If $t \geq 4$, then
there exists a frame of type $2^ut^1$ if and only if $t$ is even
and $u \geq t+1$, except possibly when $u=19$ and $t=18$.
\end{thm}

The results of this paper are accomplished by a variety of direct 
and recursive constructions, both new and old.  The constructions we
employ are summarized in the next section, including some new constructions
which should also be useful in constructing other types of designs.

\section{Constructions}
\subsection{Filling in Holes}

We first discuss the idea of Filling in Holes.

\begin{con}[Frame Filling in Holes]  
\cite{S23}
\label{con1}
Suppose there is a frame of type $\{ s_i: 1 \leq i \leq n\} $, 
and let $a\geq 0$ be an integer.  For $1 \leq i \leq n-1$, 
suppose there is an $(s_i + a,a)-$IRS.  Then there is an 
$(s+a, a)-$IRS, where $s = \sum s_i$.
\end{con}

The following construction is obtained from \cite[Construction 2.2]{SZ93}
by setting $a=b$.

\begin{con}[I$-$frame Filling in Holes]  
\cite{SZ93}
\label{con2}
Suppose there is an I$-$frame of type $\{ (s_i,t_i): 1 \leq i \leq n\} $, 
and let $a$ be a non-negative integer.  For $1 \leq i \leq n$, 
suppose there is an $(s_i + a; t_i+a) -$IRS.  
Then there is an $(s+a, t+a)-$IRS, where $s = \sum s_i$ and $t = \sum t_i$.
\end{con}

Here is a variation where we fill in holes of an I$-$frame 
in such a way that we produce another
I$-$frame.

\begin{con}[I$-$frame Filling in Holes]  
\label{ItoI}
Let $m$ be a positive integer.
Suppose there is an I$-$frame of type $(mt_1,t_1)^n(s,t_2)^1$.
Let $a$ be a non-negative integer, and  
suppose there is a frame of type ${t_1}^ma^1$. 
Then there is an I$-$frame of type
$(t_1,t_1)^{n}(t_1,0)^{n(m-1)}(s+a,t_2)^1$.
\end{con}


%Filling in holes of double frame

The following new Filling in Holes construction starts with a double frame
and yields a frame.

\begin{con}[Double Frame Filling in Holes] 
\label{dfFIH} 
Suppose there is a double frame of type $A = (a_{ij})$. 
For each $j$, $1 \leq j \leq m$, suppose there is a frame of type 
$\{a_{1j}, \dots ,a_{nj}\}$.  Then there is a frame of type
$\{s_{1}, \dots ,s_{n}\}$
where $s_i = \sum _{j=1}^{m} a_{ij}$, $1 \leq i \leq n$.
\end{con}

\subsection{Fundamental Construction}

The following recursive construction that uses group-divisible designs
is known as the Fundamental Frame Construction.

\begin{con}[Fundamental Frame Construction] 
\label{fc}
\cite{S23}  Let $(X, {\cal G}, {\cal A})$ be a 
group-divisible design, and let $w: X\rightarrow {\bf Z}^+ \cup \{ 0\}$ 
(we say that $w$ is a {\it weighting}).  
For every $A \in {\cal A}$, suppose there is a frame having type 
$\{ w(x):x \in A\} $.  Then there is a frame having type
 $\{ \sum_{x \in G}^{} w(x):  G \in {\cal G}\} $.
\end{con}

\subsection{Transversals and Inflation Constructions}
\label{s3}

In this section we give some constructions that use orthogonal 
Latin squares and generalizations to ``blow up'' the cells of a 
frame or similar object.
Before giving the constructions, some further definitions will be useful.  
Let $S$ be a set and let $\cal H$ be a set of {\it disjoint} subsets of $S$.  
A {\it holey Latin square} having {\it hole set} $\cal H$ is an 
$|S| \times |S|$ array, $L$, indexed by $S$, which satisfies 
the following properties:

\begin{enumerate}
\item every cell of $L$ either is empty or contains a symbol of $S$
\item every symbol of $S$ occurs at most once in any row or column of $L$
\item the subarrays $H \times H$ are empty, for every 
$H \in {\cal H}$ (these subarrays are referred to as {\it holes})
\item symbol $s \in S$ occurs in row or column $t$ if and only if 
\[(s, t) \in (S \times S) \backslash 
\bigcup_{H \in {\cal H}}^{} (H \times H).\]
\end{enumerate}

Two holey Latin squares on symbol set $S$ and hole set ${\cal H}$, say 
$L_1$ and $L_2$, are said to be {\it orthogonal} if their superposition 
yields every ordered pair in 
\[(S \times S) \backslash \bigcup_{H \in {\cal H}}^{} (H \times H).\]  
If ${\cal H} = \emptyset$, then a pair of orthogonal holey Latin squares on 
symbol set $S$ and hole set ${\cal H}$ is just a pair of orthogonal Latin
squares of order $|S|$, denoted MOLS$(|S|)$.

We shall use the notation IMOLS$(s; s_1, \dots , s_n)$ to denote a pair of 
orthogonal holey Latin squares on symbol set $S$ and hole set 
${\cal H} = \{ H_1, \dots , H_n\} $, where $s = |S|$, $s_i = |H_i|$ for 
$1 \leq i \leq n$,
and the $H_i$'s are disjoint.  In the special case where 
$\sum _{i=1}^{n} s_i = s$ (i.e.\ the holes are {\it spanning}), 
we use the notation HMOLS$(s; s_1, \dots , s_n)$.  The {\it type} of 
HMOLS$(s; s_1, \dots , s_n)$ is defined to be the multiset 
$\{s_1, \dots , s_n\}$.

If $T$ is the type (of a frame) 
${t_1}^{u_1}{t_2}^{u_2} \dots {t_k}^{u_k}$ and $m$ is an integer, then 
$mT$ is defined to be the type ${mt_1}^{u_1}{mt_2}^{u_2} \dots {mt_k}^{u_k}$.  
The following recursive construction is referred to as the Inflation 
Construction.  It essentially ``blows up'' every filled cell of a frame into 
MOLS$(m)$.

\begin{con} [MOLS Inflation Construction] 
\label{con3}
\cite{S23}  
Suppose there is a frame of type $T$, and suppose $m$ is a positive integer, 
$m \neq 2$ or $6$.  Then there is a frame of type $mT$.
\end{con}

Here is a version of the Inflation Construction that produces a double frame.
It uses HMOLS of type $1^m$ instead of MOLS$(m)$.

\begin{con} [HMOLS Inflation Construction] 
\label{HMOLS}  
Suppose there is a frame of type $\{s_1, \dots , s_n\}$, and 
suppose $m$ is a positive integer, $m \neq 2,3,6$.  Then there 
is a double frame of type $(a_{ij})$,
where $a_{ij} = s_i$, $1 \leq i \leq n$, $1 \leq j \leq m$.
\end{con}

In the remainder of this section, we discuss several powerful 
generalizations of the inflation construction that use transversals in
various ways.  

Suppose $F$ is an $\{ S_1, \dots , S_n\} -$Room frame, where 
$S = \bigcup S_i$.  A {\it complete transversal} is a set $T$ of $|S|$ 
filled cells in $F$ such that every symbol is contained in exactly two 
cells of $T$.  
If the pairs in the cells of $T$ are ordered so that every symbol occurs 
once as a first co-ordinate and once as a second co-ordinate in a cell 
of $T$, then $T$ is said to be an {\it ordered transversal}.  (Note that 
any transversal can be ordered, since the union of all the edges in a 
transversal forms a disjoint union of cycles.  If these cycles are 
arbitrarily oriented, then the direction of each edge provides an 
ordering for the transversal.)  

If $|S|$ is even and the cells of $T$ can be partitioned into two 
subsets $T_1$ and $T_2$ of $|S| / 2$ cells, so that every symbol 
is contained in one cell in each of $T_1$ and $T_2$, then $T$ is 
said to be {\it partitioned}.  A transversal can be partitioned if 
and only if the cycles formed from the edges in it all have even 
length.  A complete ordered partitioned (complete ordered, resp.) 
transversal will be referred to as a {\it COP transversal} 
({\it CO transversal}, resp.). 

Here is the first generalization of the Inflation Construction.

\begin{con}
\label{con4}
\cite{L20}, \cite{D10}
Suppose there is a frame of type $t^g$ having $\ell $ disjoint 
COP transversals.  For $1 \leq i \leq \ell $, let $u_i \geq 0$ be 
an integer.  Let $m$ be a positive integer, $m \neq 2$ or $6$, and 
suppose there exist IMOLS$(m+u_i;u_i)$, for $1 \leq i \leq \ell $.  
Then there is a frame of type $(mt)^g(2u)^1$, where $u = \sum u_i$.
\end{con}

In order to apply Construction \ref{con4}, it must be the case that $tg$ 
is even in order that transversals be partitionable.  We now give a 
variation in which $tg$ can be odd.  This variation uses CO transversals 
rather than COP transversals.  However, the IMOLS need an additional 
property, which will imply that $m$ must now be even.  We describe this 
property now.

Suppose $L_1$ and $L_2$ are IMOLS$(m + u; u)$ on symbol set $S$ and hole 
set ${\cal H} = \{ H\} $.  A {\it holey} row (or column) of $L_1$ or $L_2$ 
is one that meets the hole.  A holey row (or column), $T$, is said to be 
{\it partitionable} if the superposition of row (or column) $T$ of $L_1$ 
and $L_2$ can be partitioned into two subsets $T_1$ and $T_2$ of $m/2$ 
cells, so that every symbol of $S \backslash H$ is contained in one cell 
in each of $T_1$ and $T_2$.  An IMOLS$(m + u; u)$ is said to be 
{\it partitionable} if every holey row and column is partitionable. 

Finally, we use the notation ISOLS$(m + u; u)$ to denote IMOLS$(m + u; u)$ 
that are transposes of each other.  In Figure \ref{f2}, we present 
partitionable ISOLS$(5;1)$.  We present only one square, since the 
other can be obtained by transposing.

\begin{figure}[htb]
\caption{ISOLS$(5;1)$}
\label{f2}
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
$1$ & $x$ & $4$ & $3$ & $2$ \\ \hline
$3$ & $2$ & $1$ & $x$ & $4$ \\ \hline
$x$ & $4$ & $3$ & $2$ & $1$ \\ \hline
$2$ & $1$ & $x$ & $4$ & $3$ \\ \hline
$4$ & $3$ & $2$ & $1$ & \\ \hline
\end{tabular}
\end{center}
\end{figure}

\begin{con}
\label{con4.1}
\cite{DZ93}
Suppose there is a frame of type $t^g$ having $\ell $ disjoint CO 
transversals.  For $1 \leq i \leq \ell $, let $u_i \geq 0$ be an 
integer.  Let $m$ be an even positive integer, $m \neq 2$ or $6$.  
Suppose there exist partitionable IMOLS$(m+u_i;u_i)$, for 
$1 \leq i \leq \ell $.  Then there is a frame of type $(mt)^g(2u)^1$, 
where $u = \sum u_i$.
\end{con}

We also use some constructions involving frames with a different type 
of transversal.  Suppose $F$ is an $\{ S_1, \dots , S_n\} -$Room frame, 
where $S = \bigcup S_i$.  A {\it holey transversal} (with respect to 
hole $S_i$) is a set $T$ of $|S \backslash S_i|$ filled cells in $F$ 
such that every symbol of $S \backslash S_i$ is contained in exactly 
two cells of $T$.  If the pairs in the cells of $T$ are ordered so 
that every symbol of $S \backslash S_i$ occurs once as a first 
co-ordinate and once as a second co-ordinate in a cell of $T$, 
then $T$ is said to be {\it ordered} (as before, any transversal 
can be ordered).  If $|S \backslash S_i|$ is even and the cells of 
$T$ can be partitioned into two subsets $T_1$ and $T_2$ of 
$|S \backslash S_i| / 2$ cells, so that every symbol of 
$|S \backslash S_i|$ is contained in one cell in each of 
$T_1$ and $T_2$, then $T$ is said to be {\it partitioned}.  
A holey ordered partitioned (holey ordered, resp.) transversal 
will be referred to as a {\it HOP transversal} ({\it HO transversal}, resp.).

HOP transversals are used in a very similar manner as COP transversals.  
We state the following construction of Lamken and Vanstone without proof.

\begin{con}
\label{con5}
\cite{L20}, \cite{D10}
Suppose there is a frame of type ${t_1}^g{t_2}^1$ having $\ell $ disjoint 
HOP transversals with respect to the hole of size $t_2$.  For 
$1 \leq i \leq \ell $, let $u_i \geq 0$ be an integer.  Let $m$ 
be a positive integer, $m \neq 2$ or $6$, and suppose there exist 
IMOLS$(m+u_i;u_i)$, for $1 \leq i \leq \ell $.  Then there is a 
frame of type $(mt_1)^g(mt_2 + 2u)^1$, where $u = \sum u_i$.
\end{con}

We now indicate a slight extension of Construction \ref{con5} in 
which the result is an I$-$frame rather than a frame. 

\begin{con}
\label{con5.1}
Suppose there is a frame of type ${t_1}^g{t_2}^1$ having $\ell $ 
disjoint HOP transversals with respect to the hole of size $t_2$.  
For $1 \leq i \leq \ell $, let $u_i \geq 0$ be an integer.  Let
 $m$ be a positive integer, $m \neq 2$ or $6$, and suppose there 
exist IMOLS$(m+u_i;u_i,1)$, for $1 \leq i \leq \ell $.  Then there 
is an I$-$frame of type $(mt_1,t_1)^g(mt_2 + 2u,t_2)^1$, 
where $u = \sum u_i$.
\end{con}

We need one further ingredient for our last construction, 
a {\it self-orthogonal Latin square} with a {\it symmetric orthogonal mate} 
(or SOLSSOM).  A self-orthogonal Latin square (SOLS) is one that is 
orthogonal to its transpose.  The symmetric orthogonal mate (SOM) 
must be symmetric (i.e.\ equal to its transpose) and orthogonal to the SOLS.  
If the order of these squares is $m$, we denote them by SOLSSOM$(m)$.  
If the main diagonal of the SOM is constant, then the SOM is termed 
{\it unipotent}.  The SOM can be unipotent only if $m$ is even.  
In Figure \ref{f1}, we present a SOLSSOM$(4)$ in which the SOM is unipotent.

\begin{figure}[htb]
\caption{a SOLSSOM of order $4$}
\label{f1}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
$1$ & $3$ & $4$ & $2$ \\ \hline
$4$ & $2$ & $1$ & $3$ \\ \hline
$2$ & $4$ & $3$ & $1$ \\ \hline
$3$ & $1$ & $2$ & $4$ \\ \hline
\end{tabular}
\hspace{.5in}
\begin{tabular}{|c|c|c|c|}
\hline
$1$ & $2$ & $3$ & $4$ \\ \hline
$2$ & $1$ & $4$ & $3$ \\ \hline
$3$ & $4$ & $1$ & $2$ \\ \hline
$4$ & $3$ & $2$ & $1$ \\ \hline
\end{tabular}
\end{center}
\end{figure}

Here is a construction for frames having HOP transversals.

\begin{con}
\label{con4.2}
\label{SZ93}
Suppose there is a frame of type $t^g$ having $\ell $ disjoint 
CO transversals.  For $1 \leq i \leq \ell $, let $u_i \geq 0$ 
be an integer, and let $m$ be an even positive integer.  
Suppose there exists a SOLSSOM$(m)$ such that the SOM is unipotent.  
Suppose also that  there exist partitionable IMOLS$(m+u_i;u_i)$, 
for $1 \leq i \leq \ell $.  Let $k = |\{ i: u_i = 0\} |$.  
Then there is a frame of type $(mt)^g(2u)^1$, where $u = \sum u_i$, 
having $k(m-1)$ HOP transversals with respect to the hole of size $2u$.
\end{con}

\subsection{Starter-adder Constructions}
\label{sac}

Let $G$ be an additive abelian group of order $g$ and let 
$H$ be a subgroup of $G$ of order $h$, where $g-h$ is even.  
A {\it frame starter} in $G \backslash H$ is a set of 
unordered pairs $S = \{ \{s_i, t_i\} : 1 \leq i \leq  (g - h) /2 \}$ 
which satisfies the following two properties:
\begin{enumerate}
\item $\{ s_i : 1 \leq i \leq  (g - h) /2 \} \cup 
\{ t_i : 1 \leq i \leq  (g - h) /2 \} = G \backslash H$
\item $\{ \pm (s_i - t_i): 1 \leq i \leq  (g - h) /2 \} = G \backslash H$.
\end{enumerate}
An {\it adder} for $S$ is an injection
$A : S \rightarrow G \backslash H$
such that 
\[\{s_i + A(s_i,t_i): 1 \leq i \leq  (g - h) /2\} 
\cup \{t_i + A(s_i,t_i): 1 \leq i \leq  (g - h) /2\} = G \backslash H.\]

It is well-known that a frame starter and adder in $G \backslash H$ 
can be used to construct a frame of type $h^{g/h}$. 
The following lemma states that the resulting frame contains many disjoint
CO transversals. 

\begin{lem}
\label{l3.1}
Suppose there exists a frame starter and adder in $G \backslash H$,
where $|G| = g$ and $|H| = h$. 
Then there exists a frame of type $h^{g/h}$ having $(g-h)/2$ 
disjoint CO transversals.
\end{lem}

\smallskip
\noindent{\it Proof.} 
Each of the $(g-h)/2$ pairs in the frame starter gives rise to a 
CO transversal in the resulting frame.  
\qed

In the case where $H = \{ 0\}$, a frame starter $S$ is termed a {\it starter}. 
If the mapping $A$ defined by $A(s_i,t_i) = -(s_i+t_i)$ is an adder, 
then $S$ is called a {\it strong} (frame) starter. 

As mentioned above, a frame starter and adder produces a uniform frame.
Frames in which all but one hole are the same size can be produced
by the method of intransitive starter-adders described in \cite{S23}.  
Here is the definition:
Let $G$ be an abelian group of order $g$ and let $H$ be a subgroup
of order $h$, where $g$ and $h$ are both even.  Let $k$ be a positive integer.
A $2k-${\it intransitive frame starter-adder} (or IFSA) 
in $G \backslash H$ is a 
quadruple $(S,C,R,A)$, where
\begin{description}
\item [] $S = \{\{s_i,t_i\}: 1 \leq i \leq (g-h)/2 -2k\} 
\cup \{u_i : 1 \leq i \leq 2k\}$
\item [] $C = \{\{p_i,q_i\}: 1 \leq i \leq k\}$ 
\item [] $R = \{\{p'_i,q'_i\}: 1 \leq i \leq k\}$ 
\item [] $A : S \rightarrow G \backslash H$ is an injection
 that satisfies the following properties:
\begin{description}
\item [(i)] $\{s_i\} \cup \{t_i\} \cup \{p_i\} \cup \{q_i\} = G \backslash H$
\item [(ii)] $\{s_i + A(s_i,t_i)\} \cup \{t_i + A(s_i,t_i)\} 
\cup \{p_i + A(u_i)\} 
\cup \{p'_i\} \cup \{q'_i\} = G \backslash H$
\item [(ii)] $\{\pm (s_i - t_i) \} \cup \{\pm (p_i - q_i) \} 
\cup \{\pm (p'_i - q'_i) \} = G \backslash H$
\item [(iv)]
Any element $p_i - q_i$ or $p'_i - q'_i$ has even order, $1 \leq i \leq k$.
\end{description}
\end{description}
By \cite[Lemma 3.3]{S23}, a $2k-$IFSA 
in $G \backslash H$ can be used to construct a frame of type $h^{g/h}(2k)^1$.
For each $\{u_i\} \in S$, we create a pair $\{\infty _i, u_i\}$, and the
final frame contains a hole of size $2k$ on the infinite elements.

We refer to set (i) as the {\it starter} and set (ii) as the 
{\it orthogonal starter}.  $A$ is called the {\it adder}.
Also, note that each pair $\{s_i,t_i\} \in S$ gives rise to an 
HO transversal with respect
to the hole of size $2k$.

\section{Uniform Frames}

In this section we investigate frames of type $t^4$.  Recall that a frame
of type $2^4$ does not exist; and for $t \geq 4$, 
a frame of type $t^4$ exists if $t$ is even, 
$t \neq 14$, $22$, $26$, $34$, $38$, $46$, $62$,
$74$, $82$, $86$, $98$, $122$, $134$, or $146$.  Actually, we will present
a self-contained proof of the existence of frames of type $t^4$ for 
$t \equiv 2 \bmod 4$, $t \geq 6$, $t \neq 14$.

Here is the main recursive construction.

\begin{thm}
\label{t4}
Suppose there is a frame of type $\{s_1, \dots , s_n\}$, 
and for $1\leq i \leq n$,
suppose there is a frame of type ${s_i}^4$.  Then there is a frame of type
$t^4$, where $t = \sum _{i=1}^{n} s_i$.
\end{thm}

\smallskip
\noindent{\it Proof.} 
From the frame of type $\{s_1, \dots , s_n\}$, we obtain a double frame 
using Construction \ref{HMOLS}  with $m = 4$.  Then use Construction 
\ref{dfFIH}, filling in frames of types ${s_i}^4$, $1 \leq i \leq n$.
We obtain a frame of type $t^4$.
\qed

\begin{lem}
\label{u2}
Suppose $t \equiv 2 \bmod 4$, $6 \leq t \leq 46$, $t \neq 14$.
Then there is a frame of type $t^4$.
\end{lem}

\smallskip
\noindent{\it Proof.} 
Frames of types $6^4$ and $10^4$ were constructed in \cite{DS93}.
These two frames then give rise to frames of types $18^4$ and $30^4$
using Construction \ref{con3} with $m = 3$.

Next, from frames of types $4^46^1$ \cite{S23}, $4^56^1$, $4^16^5$,
and $4^26^5$ \cite{DS93}, we obtain frames of types $22^4$,
$26^4$, $34^4$ and $38^4$ by applying Theorem \ref{t4}.  From a frame of 
type $6^7$ (Theorem \ref{uf}) we likewise obtain a frame of type
$42^4$.

This leaves the case $t = 46$ to do.  We begin with a frame starter and
adder in ${\bf Z}_{10} \backslash \{0,5\}$ (see \cite{SW80}).  
The resulting frame of 
type $2^5$ has four disjoint CO transversals.  Apply Construction 
\ref{con4.1} with $\ell = 3$, $m = 4$, and $u_i = 1$ ($i = 1,2,3$).
We get a frame of type $8^56^1$.  Then apply Theorem \ref{t4}
to get a frame of type $46^4$.
\qed

\begin{lem}
Suppose $t \equiv 2 \bmod 4$, $50 \leq t \leq 206$.
Then there is a frame of type $t^4$.
\end{lem}

\smallskip
\noindent{\it Proof.}
For $11 \leq g \leq 49$, $g$ odd, there is a 
starter and adder in ${\bf Z}_g$.  So for these values of $g$, 
there is a frame of type
$1^g$ having 3 or 4 disjoint CO transversals (Lemma \ref{l3.1}).
Then apply Construction \ref{con4.1} with $\ell = 3$ or $\ell = 4$, $m = 4$, 
and $u_i = 1$ ($1 \leq i \leq \ell$).  We obtain frames of type 
$4^g6^1$ and $4^g10^1$ for these values of $g$.  Then apply Theorem \ref{t4}.
\qed

We now prove the main result of this section.

\begin{thm}
\label{uf6}
Suppose $t \equiv 2 \bmod 4$, $t \geq 6$, $t \neq 14$.
Then there is a frame of type $t^4$.
\end{thm}

\smallskip
\noindent{\it Proof.}
The cases $t \leq 206$ have already been done, so we can assume $t \geq 210$.
We can write $t = 4g + a$, where $a \in \{6,10,18,22,26,38\}$, 
$g \equiv 1 \bmod 6$, $g \geq 43$.  For such $g$, 
there is a starter and adder in 
${\bf Z}_g$ (see \cite{H12}).  This starter has $a/2$ disjoint CO transversals 
(Lemma \ref{l3.1}). Apply Construction \ref{con4.1} with $\ell = a/2$, $m = 4$, 
and $u_i = 1$ ($1 \leq i \leq \ell$), and then apply Theorem \ref{t4}.
\qed

Theorem \ref{newuf} is now an immediate consequence of
Theorems \ref{uf} and \ref{uf6}.


\section{Incomplete Room Squares}

In this section, we construct all but one of the 
incomplete Room squares listed as unknown in Theorem \ref{t1.2}.  
The following IRS are
obtained using the hill-climbing algorithm described in \cite{DS93}.
They are presented in the research report \cite{DSZrr}.

\begin{lem}
\label{small}
There exists an $(n,s)-$IRS if 
\[(n,s) \in \{(55,17), (59,17), (61,17), 
(63,17), (63,19), (65,19), (83,25)\}.\]
\end{lem}

The following lemma was given in \cite[Lemma 4.4]{SZ93}.

\begin{lem}
\label{SZl4.4}
Suppose there exists a starter and adder in ${\bf Z}_g$.  
Suppose $0 \leq u \leq 3(g-1)/2$ and 
$0 \leq k \leq 7((g-1)/2 -  \lceil (u/3) \rceil )$. 
Further, suppose there is a $(6u + 2k + 11,2u + 3)-$IRS.  
Then there is a $(24g + 6u + 2k + 11,8g + 2u + 3)-$IRS.
\end{lem}

\begin{lem}
\label{small2}
There exists an $(n,s)-$IRS if 
\[(n,s) \in \{(271,89), (275,89), (277,89), (319,105), 
(325,105), (327,105), (367,121)
\}.\]
\end{lem}

\smallskip
\noindent{\it Proof.}
These IRS are constructed by 
using Lemma \ref{SZl4.4}.  The details are given in Table \ref{tab6}.
These applications make use of the IRS constructed in Lemma \ref{small}.
\qed

\begin{table}
\caption{Construction of IRS}
\label{tab6}
\[
\begin{array}{r|c|c|clc|clc}
\multicolumn{1}{c|}{g} & \multicolumn{1}{c|}{u} & \multicolumn{1}{c|}{k} 
& \multicolumn{3}{c|}{(6u+2k+11,2u+3)} 
& \multicolumn{3}{c}{(24g+6u+2k+11,8g+2u+3)} \\ \hline
9 & 7 & 1 & \hspace{.4in} & (55,17) & \hspace{.4in} 
& \hspace{.7in} & (271,89) & \hspace{.7in}\\
9 & 7 & 3 & & (59,17) &  & & (275,89) & \\
9 & 7 & 4 & & (61,17) &  & & (277,89) & \\
11 & 7 & 1 & & (55,17) &  & & (319,105) & \\
11 & 7 & 4 & & (61,17) &  & & (325,105) & \\
11 & 7 & 5 & & (63,17) &  & & (327,105) & \\
13 & 7 & 1 & & (55,17) &  & & (367,121) &
\end{array}
\]
\end{table}

Our next construction is obtained by combining Inflation
and Filling in Holes Constructions.

\begin{lem}
\label{con5.1a}
Suppose there is a frame of type ${t_1}^g{t_2}^1$ having $\ell $ 
disjoint HOP transversals with respect to the hole of size $t_2$,
where $t_1 \geq 6$ is even, $t_1 \neq 14$.
Let $0 \leq u \leq \ell$.
Suppose also that there is a $(3t_2 + t_1 + 2u+1,t_2+1)-$IRS.
Then there exists a $(3v+t_1+2u-2,v)-$IRS, where $v = t_1g+t_2+1$.
\end{lem}

\smallskip
\noindent{\it Proof.}
Start with the frame of type ${t_1}^g{t_2}^1$ and apply 
Construction \ref{con5.1} with $m = 3$ and $u_i = 0$ or $1$, 
$1 \leq i \leq \ell$.  We obtain an I$-$frame of type 
$(3t_1,t_1)^g(3t_2+2u,t_2)^1$, where $u = \sum _{i=1}^{\ell} u_i$.
Now adjoin $t_1$ new points and apply Construction \ref{ItoI} with $a=t_1$,
$m=3$ and $s = 3t_2 + 2u$,
filling in holes 
with frames of type ${t_1}^4$.
We get an I$-$frame of type $(t_1,t_1)^g(t_1,0)^{2g}(3t_2+t_1+2u,t_2)^1$.
Then apply Construction \ref{con2} with $a=1$.
\qed

\begin{cor}
\label{c6and8}
\begin{description}
\item [(i)] Suppose there is a frame of type $6^g{t}^1$ having $\ell $ 
disjoint HOP transversals with respect to the hole of size $t$.  
Suppose also that there is a $(3t + 2u+7,t+1)-$IRS, where 
$0 \leq u \leq \ell$.
Then there exists a $(3v+2u+4,v)-$IRS, where $v = 6g+t+1$.
\item [(ii)] Suppose there is a frame of type $8^g{t}^1$ having $\ell $ 
disjoint HOP transversals with respect to the hole of size $t$.  
Suppose also that there is a $(3t + 2u + 9,t+1)-$IRS, where 
$0 \leq u \leq \ell$.
Then there exists a $(3v+2u+6,v)-$IRS, where $v = 8g+t+1$.
\end{description}
\end{cor}

Here is a further specialization of Corollary \ref{c6and8}.

\begin{cor}
\label{c6and8-2}
\begin{description}
\item [(i)] 
Suppose there is a frame of type $6^g$.
Then there exists a $(3v+4,v)-$IRS, where $v = 6g+1$.
\item [(ii)] Suppose there is a frame of type $8^g$.
Then there exists a $(3v+6,v)-$IRS, where $v = 8g+1$.
\end{description}
\end{cor}

\smallskip
\noindent{\it Proof.}
Take $t= 0$ in Corollary \ref{c6and8}; then $\ell = 0$ and $u=0$.
\qed

\begin{lem}
\label{l79}
There exists an $(n,s)-$IRS if 
\[(n,s) \in \{(79,25), (97,31), (115,37), 
(151,49), (169,55)\}.\]
\end{lem}

\smallskip
\noindent{\it Proof.}
Apply Corollary \ref{c6and8-2} (i) with $g = 4, 5, 6, 8$ and $9$.
\qed

\begin{lem}
\label{l129}
There exists an $(n,s)-$IRS if $(n,s) \in \{(129,41), (153,49)\}$.
\end{lem}

\smallskip
\noindent{\it Proof.}
Apply Corollary \ref{c6and8-2} (ii) with $g = 5$ and $6$.
\qed

\begin{lem}
\label{l109}
There exists an $(n,s)-$IRS if $(n,s) \in \{(109,35), (127,41)\}$.
\end{lem}

\smallskip
\noindent{\it Proof.}
Apply Corollary \ref{c6and8} (i) with $g \in \{5,6\}$, $t=4$ and
$\ell = u = 0$.  Frames of types $6^54^1$ and $6^64^1$ are constructed in
\cite{DS93}.
\qed


\begin{lem}
\label{k1to3}
Suppose $1 \leq k \leq 3$.  Then there exists a frame of type 
$6^4(2k)^1$ having $9-2k$ disjoint 
HOP transversals with respect to the hole of size $2k$.
\end{lem}

\smallskip
\noindent{\it Proof.}
The frames are obtained from intransitive starter-adders 
presented in the Appendix.
\qed

\begin{lem}
\label{l85}
There exists an $(n,s)-$IRS if 
\[(n,s) \in \{ (85,27), (89,27), (93,27), (95,27), (91,29), 
(95,29), (97,29), (99,31)\}.\]
\end{lem}

\smallskip
\noindent{\it Proof.}
Apply Corollary \ref{c6and8} (i) with $g=4$ and $\ell = 9-t$, 
where the values of $t$ and $u$ are given 
in Table \ref{tab7}.
The required input frames
of type $6^4t^1$ come from Lemma \ref{k1to3}.  
\qed

\begin{table}
\caption{Construction of IRS}
\label{tab7}
\[
\begin{array}{c|c|clc|clc}
\multicolumn{1}{c|}{t} & \multicolumn{1}{c|}{u} 
& \multicolumn{3}{c|}{(3t+2u+7,t+1)} 
& \multicolumn{3}{c}{(3t+2u+79,t+25)} \\ \hline
2 & 0 & \hspace{.4in} & (13,3) & \hspace{.4in} 
& \hspace{.7in} & (85,27) & \hspace{.7in}\\
2 & 2 & \hspace{.4in} & (17,3) & \hspace{.4in} 
& \hspace{.7in} & (89,27) & \hspace{.7in}\\
2 & 4 & \hspace{.4in} & (21,3) & \hspace{.4in} 
& \hspace{.7in} & (93,27) & \hspace{.7in}\\
2 & 5 & \hspace{.4in} & (23,3) & \hspace{.4in} 
& \hspace{.7in} & (95,27) & \hspace{.7in}\\
4 & 0 & \hspace{.4in} & (19,5) & \hspace{.4in} 
& \hspace{.7in} & (91,29) & \hspace{.7in}\\
4 & 2 & \hspace{.4in} & (23,5) & \hspace{.4in} 
& \hspace{.7in} & (95,29) & \hspace{.7in}\\
4 & 3 & \hspace{.4in} & (25,5) & \hspace{.4in} 
& \hspace{.7in} & (97,29) & \hspace{.7in}\\
6 & 1 & \hspace{.4in} & (27,7) & \hspace{.4in} 
& \hspace{.7in} & (99,31) & \hspace{.7in}
\end{array}
\]
\end{table}


\begin{lem}
\label{l111}
There exists a $(111,35)-$IRS.
\end{lem}

\smallskip
\noindent{\it Proof.}
Apply Corollary \ref{c6and8} (ii) with $g=4$, $t=2$ and 
$\ell =0$. We use a frame of type $8^42^1$, which is obtained from an
intransitive starter-adder presented in the Appendix.  
\qed


\begin{lem}
\label{l171}
There exists a $(171,55)-$IRS and a $(173,55)-$IRS.
\end{lem}

\smallskip
\noindent{\it Proof.}
Apply Corollary \ref{c6and8} (ii) with $g=6$, $t=6$ and 
$\ell = 12$. We use a frame of type $8^66^1$ with 12 HOP transversals 
with respect to the hole of size $6$, which is obtained from an
intransitive starter-adder presented in the Appendix.  
\qed

\begin{lem}
\label{l149}
There exists an $(n,s)-$IRS if $(n,s) \in 
\{(149, 47), (151, 47), (153, 47)\}$.
\end{lem}

\smallskip
\noindent{\it Proof.}
We first apply Construction \ref{con4.2} with $t=2$, $g=5$, $\ell = 4$, 
$u_i = 1$ for $1 \leq i \leq 4$, $m = 4$.  The ingredients required
are as follows: a frame of type $2^5$ having four CO transversals
(see the proof of Lemma \ref{u2}); a SOLSSOM$(4)$ in which the SOM is unipotent
(Figure \ref{f1}); and a partitionable ISOLS$(5; 1)$ (Figure \ref{f2}).
The result is a frame of type $8^56^1$ having three HOP transversals 
with respect to the hole of size six.

Then apply Corollary \ref{c6and8} (ii) with $g = 5$, $t =6$ 
and $\ell = 3$ to obtain the desired IRS.
\qed

\begin{lem}
\label{l139}
There exists an $(n,s)-$IRS if $(n,s) \in 
\{(139, 45), (157, 51), (175, 57)\}$.
\end{lem}

\smallskip
\noindent{\it Proof.}
These IRS are obtained by apllication of Corollary \ref{c6and8} (i).

To construct a $(139, 45)-$IRS, we begin with a frame of type $2^7$ that 
has an HOP transversal \cite[Figure 1]{St87}.  Then apply Construction
\ref{con5} with $t_1 = t_2 = 2$, $g = 6$, $\ell = 1$, $u_i = 1$ and $m = 3$.
We obtain a frame of type $6^68^1$.  Finally, apply 
Corollary \ref{c6and8} (i) with $g=6$, $t=8$, $u = \ell = 0$.

The $(157, 51)-$ and $(175, 57)-$IRS are constructed as follows.  Start
with a frame of type $2^8$ ($2^9$, resp.) having one COP transversal
(such frames can be obtained from frame starters and adders \cite{St87,SW80}).
Apply Construction \ref{con4} with $\ell = 1$, $u_1 = 1$ and $m = 3$.
This yields a frame of type $6^82^1$ ($6^92^1$, resp.).
Finally, apply 
Corollary \ref{c6and8} (i) with $g = 8$ ($g = 9$, resp.), $t= 2$, and
$u = \ell = 0$.
\qed

\begin{lem}
\label{l61}
There exists an $(n,s)-$IRS if 
\[(n,s) \in 
\{(61,19), (81,25), (143, 45), (145,47)\}.\]
\end{lem}

\smallskip
\noindent{\it Proof.}
We begin with a frame of type $2^76^1$, which is given in \cite{DSZrr}.
Apply Construction \ref{con3} with $m = 3,4$ and $7$, obtaining frames
of types $6^718^1$, $8^724^1$ and $14^742^1$.
Then apply Construction \ref{con1} to the first two frames with $a= 1$,
and apply it to the last frame with $a=3,5$, producing the desired IRS.
\qed

Theorem \ref{newirs} is now an immediate consequence of
Theorem \ref{t1.2} and Lemmas 
\ref{small}, \ref{small2}, \ref{l79}--\ref{l109}, and \ref{l85}--\ref{l61}. 

\section{Frames of Type $2^ut^1$}

In this section, we study the spectrum of frames of type $2^ut^1$.
Recall that $t$ must be even and $u \geq t+1$ for such a frame to exist.
In view of Theorem \ref{old2ut1}, we need only consider the cases where
$6 \leq t \leq 18$.  For these values of $u$, there exist frames of
type $2^ut^1$ if $u \geq 5 \left\lceil {t \over 4} \right\rceil + 20$.
 
We begin by listing in Table \ref{tab8} 
the pairs $(t,u)$ that we need to eliminate.

\begin{table}
\caption{Types $2^ut^1$ for which a frame has not been constructed}
\label{tab8}
\begin{center}
\begin{tabular}{r|c}
\multicolumn{1}{c|}{$t$} & \multicolumn{1}{c}{$u$} \\ \hline
6 & 7 -- 29 \\
8 & 9 -- 29 \\
10 & 11 -- 34 \\
12 & 13 -- 34 \\
14 & 15 -- 39 \\
16 & 17 -- 39\\
18 & 19 -- 44
\end{tabular}
\end{center}
\end{table}

\begin{lem}
There exists a frame of type $2^ut^1$ for all pairs $(t, u)$
such that $t$ is even, $10 \leq t \leq 18$ and $25 \leq u \leq 44$.
\end{lem}

\smallskip
\noindent{\it Proof.}
Give weight 2 or 4 to every point in a transversal design TD$(6,5)$ 
so that the sum of the 
weights of the points in one of the groups is $t$, and the sum of 
the weights of all the points is $2u+t$.  Apply Construction \ref{fc},
filling in frames of type $2^a4^{6-b}$ \cite{DS90}.  The resulting frame
has order $2u+t$ and has a hole of size $t$.  
Then apply Construction \ref{con1} with $a = 0$.
Other than the size $t$ hole, the holes have 
(even) size at least 10 and at most 18, so they can be filled in with frames
of type $2^n$ ($5 \leq n \leq 9$).
\qed

\begin{lem}
There exist frames of type $2^{28}6^1$ and $2^{29}6^1$.
\end{lem}

\smallskip
\noindent{\it Proof.}
Start with frames of types $2^{21}20^1$ and $2^{22}20^1$ and fill in the
size 20 hole with a frame of type $2^76^1$, which is given in the research
report \cite{DSZrr}.
\qed

\begin{lem}
There exist frames of types $2^{12}10^1$, $2^{16}10^1$, 
$2^{15}12^1$, $2^{15}14^1$, $2^{20}10^1$, $2^{20}12^1$, $2^{20}14^1$, 
$2^{18}12^1$, $2^{18}14^1$, $2^{18}16^1$ and $2^{24}18^1$.
\end{lem}

\smallskip
\noindent{\it Proof.}
In each case, we start with a frame of type $t^u$, and adjoin $a$ new points,
applying Construction \ref{con1}.
We fill in frames of types $2^{t/2}a^1$ into all but one hole.
This yields a frame of type $2^{t(u-1)/2}(t+a)^1$.
The applications of this construction are presented in Table \ref{tab9}.
\qed

\begin{table}
\caption{Frames of type $2^ut^1$}
\label{tab9}
\[
\begin{array}{r|r|r|rlr|rlr}
\multicolumn{1}{c|}{t} & \multicolumn{1}{c|}{u} & \multicolumn{1}{c|}{a} 
& \multicolumn{3}{c|}{2^{t/2}a^1} & \multicolumn{3}{c}{2^{t(u-1)/2}(t+a)^1}
\\ \hline
8 & 4 & 2 & \hspace{.1in} & 2^5 & \hspace{.1in} 
& \hspace{.25in} & 2^{12}10^1 & \hspace{.25in}\\
8 & 5 & 2 & & 2^5 & & &  2^{16}10^1 &\\
10 & 4 & 2 & & 2^6 & & &  2^{15}12^1 &\\
10 & 4 & 4 & & 2^54^1 & & &  2^{15}14^1 &\\
10 & 5 & 0 & & 2^5 & & &  2^{20}10^1 &\\
10 & 5 & 2 & & 2^6 & & &  2^{20}12^1 &\\
10 & 5 & 4 & & 2^54^1 & & &  2^{20}14^1 &\\
12 & 4 & 0 & & 2^6 & & &  2^{18}12^1 &\\
12 & 4 & 2 & & 2^7 & & &  2^{18}14^1 &\\
12 & 4 & 4 & & 2^64^1 & & &  2^{18}16^1 &\\
16 & 4 & 2 & & 2^9 & & &  2^{24}18^1 &
\end{array}
\]
\end{table}

\begin{lem}
There exists a frame of type $2^{24}t^1$ for $t$ even, $6 \leq t \leq 16$.
\end{lem}

\smallskip
\noindent{\it Proof.}
Give weight three to every point in a TD$(5,4)$, 
except for $b$ points in the last group which get weight one. 
Apply Construction \ref{fc},
filling in frames of type $3^5$ and $3^41^1$ \cite{DS93}.  The resulting frame
has type $12^4(12-2b)^1$, $0 \leq b \leq 4$.  
Then apply Construction \ref{con1} with $a = 0,2$ or $4$.
The holes  
can be filled in with frames
of type $2^6a^1$, producing a frame of type $2^{24}(12-2b+a)^1$.
This yields frames of the desired types.
\qed

\begin{lem}
There exist frames of types $2^{25}6^1$ and $2^{25}8^1$.
\end{lem}

\smallskip
\noindent{\it Proof.}
Delete one or two points from a group of a TD$(6,5)$,
and give weight two to each point of the resulting design.  
Apply Construction \ref{fc},
filling in frames of type $2^5$ and $2^6$.  
We get frames of types $10^56^1$ and $10^58^1$.  
Then apply Construction \ref{con1} with $a = 0$,
filling in the size 10 holes with frames of type $2^5$.
\qed

\begin{lem}
There exist frames of types $2^{21}10^1$ and $2^{22}10^1$.
\end{lem}

\smallskip
\noindent{\it Proof.}
Give weight two to every point of a TD$(5,5)$.  
Apply Construction \ref{fc},
filling in frames of type $2^5$, to produce a 
frame of type $10^5$.  Note that any block of the TD gives rise to a
sub-frame of type $2^5$.

Now adjoin $a = 2$ or $4$ points, filling in frames of type $2^5a^1$ into
four holes.  This gives a frame of type $2^{20}(10+a)^1$ having a subframe of
type $2^5$.  Now fill in the size $10+a$ hole with a frame of type
$2^{5+a/2}$.  We get a frame of type $2^{25+a/2}$ that has a sub-frame of 
type $2^5$.  Finally, deleting the subframe produces a frame of
type $2^{20 + a/2}10^1$.
\qed

\begin{lem}
There exist frames of types $2^{u}16^1$ for $u = 17$, $21$, $22$ and $23$.
\end{lem}

\smallskip
\noindent{\it Proof.}
There is a frame starter and adder in 
$\left( {\bf Z}_4 \times {\bf Z}_4 \right) \backslash
\{(0,0), (0,2), (2, 0), (2,2)\}$ (see \cite[Lemma 5.1]{S23}).  
This gives rise to a
frame of type $4^4$ having six disjoint COP transversals.  Apply Construction
\ref{con5.1} with $t_1 = 4$, $t_2 = 0$, $g= 4$, $\ell =6$, 
$u_i = 0$ or $1$ ($1 \leq i \leq 6$) and $m = 3$.  We get an I$-$frame of
type $(12,4)^4(2u,0)^1$, where $0 \leq u \leq 6$.

Now, for $u = 0, 4, 5, 6$ we will fill in holes of this I$-$frame.
Adjoin two new points and fill in the size 12 
holes with frames of type $2^54^1$.  The size $2u$ hole is filled in with 
a frame of type $2^{u+1}$.  This yields the four desired frames.
\qed

\begin{lem}
There exist frames of types $2^{u}18^1$ for $20 \leq u \leq 23$.
\end{lem}

\smallskip
\noindent{\it Proof.}
There is a frame starter and adder in 
$\left( \left( {\bf Z}_4 \times {\bf Z}_4\right) \backslash
\{(0,0), (0,2), (2, 0), (2,2)\} \right) \cup \{\infty _1 , \infty _2\}$ 
(see \cite[Figure 5.2]{S23}).  This gives rise to a
frame of type $4^42^1$ having four disjoint HOP transversals with 
respect to the hole of size 2.  Apply Construction
\ref{con5.1} with $t_1 = 4$, $t_2 = 2$, $g = 4$, $\ell = 4$, 
$u_i = 0$ or $1$ ($1 \leq i \leq 4$) and $m = 3$.  We get an I$-$frame of
type $(12,4)^4(2u+6,2)^1$, where $0 \leq u \leq 4$.

Now, for $u = 1, 2, 3, 4$ we will fill in holes of this I$-$frame.
Adjoin two new points and fill in the size 12 
holes with frames of type $2^54^1$.  The size $2u+6$ hole is filled in with 
a frame of type $2^{u+4}$.  This yields the four desired frames.
\qed

The following was shown in \cite[Example 2.3]{G99}.

\begin{lem}
There exists a frame of type $2^86^1$.
\end{lem}

The remaining frames of type $2^ut^1$, except type $2^{19}18^1$,
are presented in the research report
\cite{DSZrr}.

\section{Comments}
 
We have nearly completed three different spectra of Room frames,
leaving one possible exception in each case.  The three exceptions
are too ``small'' to be handled by our recursive contructions.
On the other hand, they are too ``big'' 
to be easily found by direct methods (in particular,
by the hill-climbing algorithm \cite{DS87,DS93}), though we have expended 
condsiderable computer time searching for them.  

\section*{Acknowledgements}

Part of this research was done while the second author was 
visiting the University of Nebraska--Lincoln in March 1994, with support from 
the Center for Communication and Information Science at the 
University of Nebraska.  Research of D.\ R.\ Stinson is supported 
by NSF grant CCR-9121051 and NSA grant 904-93-H-3049.


\begin{thebibliography}{10}

\bibitem{DL93}
{\sc J.~H. Dinitz and E.~R. Lamken.}
\newblock Uniform Room frames with five holes.
\newblock {\em J.\ Combin.\ Designs} {\bf 1} (1993), 323--328.

\bibitem{D10}
{\sc J.~H. Dinitz and E.~R. Lamken.}
\newblock {H}owell designs with subdesigns.
\newblock {\em J.\ Combin.\ Theory A} {\bf 65} (1994), 268--301.

\bibitem{D13}
{\sc J.~H. Dinitz and D.~R. Stinson.}
\newblock Further results on frames.
\newblock {\em Ars Combinatoria} {\bf 11} (1981), 275--288.

\bibitem{DS87}
{\sc J.~H. Dinitz and D.~R. Stinson}.
A hill-climbing algorithm for the construction of one-factorizations
and Room squares.
{\em SIAM J.\ on Algebraic and Discrete Methods} {\bf 8} (1987), 430--438.

\bibitem{DS90}
{\sc J.~H. Dinitz and D.~R. Stinson}.
\newblock On the existence of Room squares with subsquares.
\newblock {\em Contemporary Mathematics} {\bf 111} (1990), 73--91.

\bibitem{DS92}
{\sc J.~H. Dinitz and D.~R. Stinson.}
\newblock {R}oom squares and related designs.
\newblock In ``Contemporary Design Theory:  A Collection of Surveys'',
John Wiley \& Sons, 1992, pp. 137--204.

\bibitem{DS93}
{\sc J.~H. Dinitz and D.~R. Stinson.}
\newblock A few more {R}oom frames.
\newblock In ``Graphs, Matrices and Designs'',
Marcel Dekker, 1993, pp. 133--146.

\bibitem{DSZrr}
{\sc J.~H. Dinitz, D.~R. Stinson and L.~Zhu.}
\newblock Some new frames.
\newblock Research Report (available in the ``Comments'' file for this paper).

\bibitem{DZ93}
{\sc B.~Du and L.~Zhu.}
\newblock The existence of incomplete Room squares.
\newblock {\em J.\ Combin.\ Math.\ Combin.\ Comput.} {\bf 14} (1993), 183--192.

\bibitem{G99}
{\sc G.~Ge.}
\newblock On the existence of Room frames of type $2^nu^1$.
\newblock {\em J.\ Statist.\ Plan.\ Infer.}, to appear.

\bibitem{GZ93}
{\sc G.~Ge and L.~Zhu.}
\newblock On the existence of Room frames of type $t^u$ for $u = 4$ and $5$.
\newblock {\em J.\ Combin.\ Designs} {\bf 1} (1993), 183--191.

\bibitem{GZ99}
{\sc G.~Ge and L.~Zhu.}
\newblock Existence of Room frames of type $2^nu^1$.
\newblock {\em J.\ Combin.\ Math.\ Combin.\ Comput.}, to appear.

\bibitem{H12}
{\sc J.~D. Horton.}
\newblock Orthogonal starters in finite abelian groups.
\newblock {\em Discrete Math.} {\bf 79} (1989/90), 265--278.

\bibitem{L20}
{\sc E.~R. Lamken and S.~A. Vanstone.}
\newblock The existence of skew {H}owell designs of side $2n$ 
and order $2n + 2$.
\newblock {\em J.\ Combin.\ Theory A} {\bf 54} (1980), 20--40.

\bibitem{M25}
{\sc R.~C. Mullin and W.~D. Wallis.}
\newblock The existence of {R}oom squares.
\newblock {\em Aequationes Math.} {\bf 13} (1975), 1--7.

\bibitem{S23}
{\sc D.~R. Stinson.}
\newblock Some constructions for frames, {R}oom squares, and subsquares.
\newblock {\em Ars Combinatoria} {\bf 12} (1981), 229--267.

\bibitem{St87}
{\sc D.~R. Stinson.}
\newblock On the existence of skew Room frames of type $2^n$.
\newblock {\em Ars Combinatoria} {\bf 24} (1987), 115--128.

\bibitem{SW80}
{\sc D.~R. Stinson and W.~D. Wallis}.
\newblock Some designs used in constructing skew Room squares.
\newblock {\em Ann.\ Discrete Math.} {\bf 8} (1980), 171--175.

\bibitem{SZ93}
{\sc D.~R. Stinson and L.~Zhu}.
\newblock Towards the spectrum of Room squares with subsquares.
\newblock {\em J.\ Combin.\ Theory A} {\bf 63} (1993), 129--142.

\end{thebibliography}


\newpage
\appendix
\section*{Appendix:  Some Intransitive Starter-adders}

In this Appendix, we construct some new frames using the 
method of intransitive starter-adders described in Section \ref{sac}.
In each case, we list the type of the frame, together with
the starter, the adder and the orthogonal starter.
(In our presentation, we also include the ``infinite elements''.)
We construct a frame of type ${t_1}^ut_2$ from a $t_2-$IFSA in 
\[\left( {\bf Z}_{t_1u} \backslash \{iu: 0 \leq i \leq t_1-1\} \right) 
\cup \{\infty _j : 1 \leq j \leq t_2\}.\]

\begin{center}
\begin{tabular}[t]{|l|crc|l|}
\hline
\multicolumn{5}{|c|}{type $6^42^1$} \\
\hline
\multicolumn{1}{|c|}{starter} & \multicolumn{3}{c|}{adder} 
& \multicolumn{1}{c|}{starter} \\
\hline
$\{7, \infty _1\}$ & & $10$ & & $\{17, \infty _1\}$ \\
$\{23, \infty _2\}$ & & $11$ & & $\{10, \infty _2\}$ \\
$\{1, 2\}$ & & $17$ & & $\{18, 19\}$ \\
$\{3, 5\}$ & & $22$ & & $\{1, 3\}$ \\
$\{6, 11\}$ & & $3$ & & $\{9, 14\}$ \\
$\{14, 17\}$ & & $9$ & & $\{23, 2\}$ \\
$\{13, 19\}$ & & $18$ & & $\{7, 13\}$ \\
$\{15, 22\}$ & & $7$ & & $\{22, 5\}$ \\
$\{9, 18\}$ & & $21$ & & $\{6, 15\}$ \\ \hline
$\{10, 21\}$ & & & &  \\ \hline
 & & & & $\{11, 21\}$ \\
\hline
\end{tabular}
\hspace{.5in}
%\end{center}
%
%\begin{center}
\begin{tabular}[t]{|l|crc|l|}
\hline
\multicolumn{5}{|c|}{type $6^44^1$} \\
\hline
\multicolumn{1}{|c|}{starter} & \multicolumn{3}{c|}{adder} 
& \multicolumn{1}{c|}{starter} \\
\hline
$\{15, \infty _1\}$ & & $23$ & & $\{14, \infty _1\}$ \\
$\{5, \infty _2\}$ & & $21$ & & $\{2, \infty _2\}$ \\
$\{6, \infty _3\}$ & & $17$ & & $\{23, \infty _3\}$ \\
$\{10, \infty _4\}$ & & $15$ & & $\{1, \infty _4\}$ \\
$\{17, 19\}$ & & $22$ & & $\{15, 17\}$ \\
$\{18, 23\}$ & & $19$ & & $\{13, 18\}$ \\
$\{1, 11\}$ & & $18$ & & $\{19, 5\}$ \\
$\{13, 7\}$ & & $14$ & & $\{3, 21\}$ \\
$\{21, 22\}$ & & $13$ & & $\{10, 11\}$ \\ \hline
$\{3, 14\}$ & & & &  \\
$\{2, 9\}$ & & & &  \\ \hline
 & & & & $\{6, 9\}$ \\
 & & & & $\{7, 22\}$ \\
\hline
\end{tabular}
\end{center}

\vspace{.25in}

\begin{center}
\begin{tabular}[t]{|l|crc|l|}
\hline
\multicolumn{5}{|c|}{type $6^46^1$} \\
\hline
\multicolumn{1}{|c|}{starter} & \multicolumn{3}{c|}{adder} 
& \multicolumn{1}{c|}{starter} \\
\hline
$\{2, \infty _1\}$ & & $1$ & & $\{3, \infty _1\}$ \\
$\{9, \infty _2\}$ & & $2$ & & $\{11, \infty _2\}$ \\
$\{18, \infty _3\}$ & & $5$ & & $\{23, \infty _3\}$ \\
$\{1, \infty _4\}$ & & $13$ & & $\{14, \infty _4\}$ \\
$\{19, \infty _5\}$ & & $18$ & & $\{13, \infty _5\}$ \\
$\{11, \infty _6\}$ & & $19$ & & $\{6, \infty _6\}$ \\
$\{10, 13\}$ & & $21$ & & $\{7, 10\}$ \\
$\{7, 17\}$ & & $22$ & & $\{5, 15\}$ \\
$\{3, 22\}$ & & $23$ & & $\{2, 21\}$ \\ \hline
$\{5, 23\}$ & & & &  \\
$\{6, 21\}$ & & & &  \\
$\{14, 15\}$ & & & &  \\ \hline
 & & & & $\{1, 18\}$ \\
 & & & & $\{9, 22\}$ \\
 & & & & $\{17, 19\}$ \\
\hline
\end{tabular}
\hspace{.5in}
%\end{center}
%
%begin{center}
\begin{tabular}[t]{|l|crc|l|}
\hline
\multicolumn{5}{|c|}{type $8^42^1$} \\
\hline
\multicolumn{1}{|c|}{starter} & \multicolumn{3}{c|}{adder} 
& \multicolumn{1}{c|}{starter} \\
\hline
$\{9, \infty _1\}$ & & $9$ & & $\{18, \infty _1\}$ \\
$\{31, \infty _2\}$ & & $10$ & & $\{9, \infty _2\}$ \\
$\{1, 2\}$ & & $5$ & & $\{6, 7\}$ \\
$\{3, 5\}$ & & $18$ & & $\{21, 23\}$ \\
$\{27, 30\}$ & & $3$ & & $\{30, 1\}$ \\ 
$\{6, 11\}$ & & $23$ & & $\{29, 2\}$ \\ 
$\{17, 23\}$ & & $2$ & & $\{19, 25\}$ \\ 
$\{14, 21\}$ & & $21$ & & $\{3, 10\}$ \\ 
$\{10, 19\}$ & & $7$ & & $\{17, 26\}$ \\ 
$\{15, 25\}$ & & $22$ & & $\{5, 15\}$ \\ 
$\{18, 29\}$ & & $25$ & & $\{11, 22\}$ \\ 
$\{13, 26\}$ & & $1$ & & $\{14, 27\}$ \\ 
\hline
$\{7, 22\}$ & & & &  \\ \hline
 & & & & $\{13, 31\}$ \\
\hline
\end{tabular}
\end{center}


\begin{center}
\begin{tabular}[t]{|l|crc|l|}
\hline
\multicolumn{5}{|c|}{type $8^66^1$} \\
\hline
\multicolumn{1}{|c|}{starter} & \multicolumn{3}{c|}{adder} 
& \multicolumn{1}{c|}{starter} \\
\hline
$\{2, \infty _1\}$ & & $5$ & & $\{7, \infty _1\}$ \\
$\{8, \infty _2\}$ & & $13$ & & $\{21, \infty _2\}$ \\
$\{15, \infty _3\}$ & & $29$ & & $\{44, \infty _3\}$ \\
$\{26, \infty _4\}$ & & $7$ & & $\{33, \infty _4\}$ \\
$\{35, \infty _5\}$ & & $3$ & & $\{38, \infty _5\}$ \\
$\{41, \infty _6\}$ & & $8$ & & $\{1, \infty _6\}$ \\
$\{5, 9\}$ & & $47$ & & $\{4, 8\}$ \\
$\{43, 45\}$ & & $46$ & & $\{41, 43\}$ \\
$\{32, 40\}$ & & $45$ & & $\{29, 37\}$ \\ 
$\{44, 23\}$ & & $44$ & & $\{40, 19\}$ \\ 
$\{10, 19\}$ & & $43$ & & $\{5, 14\}$ \\ 
$\{46, 29\}$ & & $41$ & & $\{39, 22\}$ \\ 
$\{28, 39\}$ & & $40$ & & $\{20, 31\}$ \\ 
$\{20, 34\}$ & & $39$ & & $\{11, 25\}$ \\ 
$\{21, 37\}$ & & $37$ & & $\{10, 26\}$ \\ 
$\{47, 22\}$ & & $35$ & & $\{34, 9\}$ \\ 
$\{27, 17\}$ & & $34$ & & $\{13, 3\}$ \\ 
$\{38, 31\}$ & & $33$ & & $\{23, 16\}$ \\ 
$\{11, 16\}$ & & $16$ & & $\{27, 32\}$ \\ 
$\{33, 13\}$ & & $2$ & & $\{35, 15\}$ \\ 
\hline
$\{14, 1\}$ & & & &  \\
$\{4, 7\}$ & & & &  \\ 
$\{25, 3\}$ & & & &  \\  \hline
 & & & & $\{2, 17\}$ \\
 & & & & $\{45, 46\}$ \\
 & & & & $\{47, 28\}$ \\
\hline
\end{tabular}
\end{center}

\end{document}