On the Spectra of Certain Classes of Room Frames

Jeffrey H. Dinitz Department of Mathematics

University of Vermont Burlington, Vermont 05405, USA

Douglas R. Stinson

Computer Science and Engineering Department and Center for Communication and Information Science

University of Nebraska-Lincoln Lincoln, Nebraska 68588, USA

L. Zhu

Department of Mathematics Suzhou University, Suzhou 215006

People’s Republic of China

Submitted: June 14, 1994; Accepted: September 14, 1994.

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^{u}t^{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. Math reviews classification: 05B15

1 Introduction

Room squares and generalizations have been extensively studied for over 35 years. In 1974, Mullin and Wallis [15] 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 [6].) In this paper, we study three well-known spectra:

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 [6]. Two more recent papers are [19, 9].

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 [3]. The history up to 1992 is found in [6] and more recent results appear in [11, 1].

Room frames of type 2^{u}t^{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 [10, 12].

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 ∞ be a “special” symbol not in S, and let H be a set of subsets of S. A holey Room square having hole set H is an |S| × |S| array, F, indexed by S, which satisfies the following properties:

1. Every cell of F either is empty or contains an unordered pair of symbols of S ⋃{∞}.

2. Every symbol of S ⋃{∞} 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.

3. The subarrays H × H are empty, for every H ∈ H (these subarrays are referred to as holes).

4. The symbol s ∈ S occurs in row or column t if and only if

(s, t) ∈ (S × S)\ ⋃_{H∈H}(H × H);

and symbol ∞ occurs in row or column t if and only if

t ∈ S\ ⋃_{H∈H} H.

5. The pair {s, t} occurs in F if and only if

(s, t) ∈ (S × S)\ ⋃_{H∈H}(H × H);

the pair {∞, t} occurs in F if and only if

t ∈ S\ ⋃_{H∈H} H.

The holey Room square F will be denoted as HRS(H). The order of F is |S|. Note that ∞ does not occur in any cell of F if ⋃_{H∈H} H = S.

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

If H = {S_{1}, …, S_{n}} is a partition of S, then an HRS(H) is called a Room frame. As is usually done in the literature, we refer to a Room frame simply as a frame. The type of the frame is defined to be the multiset {|S_{i}| : 1 ≤ i ≤ n}. We usually use an “exponential” notation to describe types: a type t_{1}^{u_{1}}t_{2}^{u_{2}} … t_{k}^{u_{k}} denotes u_{i} occurrences of t_{i}, 1 ≤ i ≤ k.

We do not display any specific Room frames in this paper, but examples are shown in numerous papers, such as [6] and [7].

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 H = {S_{1}, …, S_{n}, T } , where {S_{1}, …, S_{n}} is a partition of S, then an HRS(H) is called an incomplete frame or an I−frame. The type of the I−frame is defined to be the multiset {(|S_{i}|, |S_{i} ⋂ T |) : 1 ≤ i ≤ n}. We may also use an “exponential” notation to describe types of I−frames.

We also make use of a new type of HRS. Suppose H = {S_{1}, …, S_{n}, T_{1}, …, T_{m}}, where {S_{1}, …, S_{n}} and {T_{1}, …, T_{m}} are both partitions of S. Then an HRS(H) is called a double frame. For 1 ≤ i ≤ n, 1 ≤ j ≤ m, define a_{ij} = |S_{i} ∩ T_{j}|. Then the type of the double frame HRS(H) is defined to be the n × 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 [15].

Theorem 1.1 [15] A Room square of side n exists if and only if n is odd and n ≠ 3 or 5.

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

Theorem 1.2 [3, 11, 1] Suppose t and u are positive integers, u ≥ 4, and (t, u) ≠ (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.

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

Theorem 1.3 [19, 9] Suppose n and s are odd positive integers, n ≥ 3s + 2, and (n, s) ≠ (5, 1). Then there exists an (n, s)−IRS except possibly for the following 45 ordered pairs:

(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).

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^{u}t^{1}. Frames of these types were studied in [10, 12], where the following results were proved.

Theorem 1.4 [10, 12] Suppose t and u are positive integers. If t ≥ 20 or t = 4, then there exists a frame of type 2^{u}t^{1} if and only if t is even and u ≥ t + 1. Also, for 6 ≤ t ≤ 18, there exists a frame of type 2^{u}t^{1} if t is even and u ≥ 5 ⌈\frac{t}{4}⌉ + 20.

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:

Theorem 1.5 Suppose t and u are positive integers, u ≥ 4, and (t, u) ≠ (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.

We construct IRS for 44 of the 45 exceptions given in Theorem 1.3, so the following theorem results:

Theorem 1.6 Suppose n and s are odd positive integers, n ≥ 3s + 2, and (n, s) ≠ (5, 1). Then there exists an (n, s)−IRS, except possibly for (n, s) = (67, 21).

For Room frames of type 2^{u}t^{1}, we can also eliminate all but one of the possible exceptions, producing the following theorem:

Theorem 1.7 Suppose t and u are positive integers. If t ≥ 4, then there exists a frame of type 2^{u}t^{1} if and only if t is even and u ≥ t + 1, except possibly when u = 19 and t = 18.

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.

2 Constructions

2.1 Filling in Holes

We first discuss the idea of Filling in Holes.

Construction 2.1 (Frame Filling in Holes) [16] Suppose there is a frame of type {s_{i} : 1 ≤ i ≤ n}, and let a ≥ 0 be an integer. For 1 ≤ i ≤ n − 1, suppose there is an (s_{i} + a, a)−IRS. Then there is an (s + a, a)−IRS, where s = ∑ s_{i}.

The following construction is obtained from [19, Construction 2.2] by setting a = b.

Construction 2.2 (I−frame Filling in Holes) [19] Suppose there is an I−frame of type {(s_{i}, t_{i}) : 1 ≤ i ≤ n}, and let a be a non-negative integer. For 1 ≤ i ≤ n, suppose there is an (s_{i} + a; t_{i} + a)−IRS. Then there is an (s + a, t + a)−IRS, where s = ∑ s_{i} and t = ∑ t_{i}.

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

Construction 2.3 (I−frame Filling in Holes) 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}^{m}a^{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}.

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

Construction 2.4 (Double Frame Filling in Holes) Suppose there is a double frame of type A = (a_{ij}). For each j, 1 ≤ j ≤ m, suppose there is a frame of type {a_{1j}, …, a_{nj}}. Then there is a frame of type {s_{1}, …, s_{n}} where s_{i} = ∑_{j=1}^{m} a_{ij}, 1 ≤ i ≤ n.

2.2 Fundamental Construction

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

Construction 2.5 (Fundamental Frame Construction) [16] Let (X, G, A) be a group-divisible design, and let w : X → Z^{+} ∪ {0} (we say that w is a weighting). For every A ∈ A, suppose there is a frame having type {w(x) : x ∈ A}. Then there is a frame having type {∑_{x∈G} w(x) : G ∈ G}.

2.3 Transversals and Inflation Constructions

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 H be a set of disjoint subsets of S. A holey Latin square having hole set H is an |S| × |S| array, L, indexed by S, which satisfies the following properties:

1. every cell of L either is empty or contains a symbol of S

2. every symbol of S occurs at most once in any row or column of L

3. the subarrays H × H are empty, for every H ∈ H (these subarrays are referred to as holes)

4. symbol s ∈ S occurs in row or column t if and only if

(s, t) ∈ (S × S)\ ⋃_{H∈H}(H × H).

Two holey Latin squares on symbol set S and hole set H, say L_{1} and L_{2}, are said to be orthogonal if their superposition yields every ordered pair in

(S × S)\ ⋃_{H∈H}(H × H).

If H = ∅, then a pair of orthogonal holey Latin squares on symbol set S and hole set H is just a pair of orthogonal Latin squares of order |S|, denoted MOLS(|S|).

We shall use the notation IMOLS(s; s_{1}, …, s_{n}) to denote a pair of orthogonal holey Latin squares on symbol set S and hole set H = {H_{1}, …, H_{n}}, where s = |S|, s_{i} = |H_{i}| for 1 ≤ i ≤ n, and the H_{i}’s are disjoint. In the special case where ∑_{i=1}^{n} s_{i} = s (i.e. the holes are spanning), we use the notation HMOLS(s; s_{1}, …, s_{n}). The type of HMOLS(s; s_{1}, …, s_{n}) is defined to be the multiset {s_{1}, …, s_{n}}.

If T is the type (of a frame) t_{1}^{u_{1}}t_{2}^{u_{2}} … 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}} … 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).

Construction 2.6 (MOLS Inflation Construction) [16] Suppose there is a frame of type T, and suppose m is a positive integer, m ≠ 2 or 6. Then there is a frame of type mT.

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

Construction 2.7 (HMOLS Inflation Construction) Suppose there is a frame of type {s_{1}, …, s_{n}}, and suppose m is a positive integer, m ≠ 2, 3, 6. Then there is a double frame of type (a_{ij}), where a_{ij} = s_{i}, 1 ≤ i ≤ n, 1 ≤ j ≤ m.

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}, …, S_{n}}−Room frame, where S = ⋃ S_{i}. A 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 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 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 COP transversal (CO transversal, resp.).

Here is the first generalization of the Inflation Construction.

Construction 2.8 [14], [2] Suppose there is a frame of type t^{g} having ℓ disjoint COP transversals. For 1 ≤ i ≤ ℓ, let u_{i} ≥ 0 be an integer. Let m be a positive integer, m ≠ 2 or 6, and suppose there exist IMOLS(m + u_{i}; u_{i}), for 1 ≤ i ≤ ℓ. Then there is a frame of type (mt)^{g}(2u)^{1}, where u = ∑ u_{i}.

In order to apply Construction 2.8, 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 H = {H}. A 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 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\H is contained in one cell in each of T_{1} and T_{2}. An IMOLS(m + u; u) is said to be 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 1, we present partitionable ISOLS(5; 1). We present only one square, since the other can be obtained by transposing.

Construction 2.9 [9] Suppose there is a frame of type t^{g} having ℓ disjoint CO transversals. For 1 ≤ i ≤ ℓ, let u_{i} ≥ 0 be an integer. Let m be an even positive integer, m ≠ 2 or 6. Suppose there exist partitionable IMOLS(m + u_{i}; u_{i}), for 1 ≤ i ≤ ℓ. Then there is a frame of type (mt)^{g}(2u)^{1}, where u = ∑ u_{i}.

We also use some constructions involving frames with a different type of transversal. Suppose F is an {S_{1}, …, S_{n}}−Room frame, where S = ⋃ S_{i}. A holey transversal (with respect to hole S_{i}) is a set T of |S\S_{i}| filled cells in F such that every symbol Figure 1: ISOLS(5; 1)

1 x 4 3 2
3 2 1 x 4
x 4 3 2 1
2 1 x 4 3
4 3 2 1

of S\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\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 ordered (as before, any transversal can be ordered). If |S\S_{i}| is even and the cells of T can be partitioned into two subsets T_{1} and T_{2} of |S\S_{i}|/2 cells, so that every symbol of |S\S_{i}| is contained in one cell in each of T_{1} and T_{2}, then T is said to be partitioned. A holey ordered partitioned (holey ordered, resp.) transversal will be referred to as a HOP transversal (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.

Construction 2.10 [14], [2] Suppose there is a frame of type t_{1}^{g}t_{2}^{1} having ℓ disjoint HOP transversals with respect to the hole of size t_{2}. For 1 ≤ i ≤ ℓ, let u_{i} ≥ 0 be an integer. Let m be a positive integer, m ≠ 2 or 6, and suppose there exist IMOLS(m + u_{i}; u_{i}), for 1 ≤ i ≤ ℓ. Then there is a frame of type (mt_{1})^{g}(mt_{2} + 2u)^{1}, where u = ∑ u_{i}.

We now indicate a slight extension of Construction 2.10 in which the result is an I−frame rather than a frame.

Construction 2.11 Suppose there is a frame of type t_{1}^{g}t_{2}^{1} having ℓ disjoint HOP transversals with respect to the hole of size t_{2}. For 1 ≤ i ≤ ℓ, let u_{i} ≥ 0 be an integer. Let m be a positive integer, m ≠ 2 or 6, and suppose there exist IMOLS(m+u_{i}; u_{i}, 1), for 1 ≤ i ≤ ℓ. Then there is an I−frame of type (mt_{1}, t_{1})^{g}(mt_{2} + 2u, t_{2})^{1}, where u = ∑ u_{i}.

We need one further ingredient for our last construction, a self-orthogonal Latin square with a 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 unipotent. The SOM can be unipotent only if m is even. In Figure 2, we present a SOLSSOM(4) in which the SOM is unipotent.

Here is a construction for frames having HOP transversals.

Figure 2: a SOLSSOM of order 4

1 3 4 2 4 2 1 3 2 4 3 1 3 1 2 4  1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1

Construction 2.12 Suppose there is a frame of type t^{g} having ℓ disjoint CO transversals. For 1 ≤ i ≤ ℓ, let u_{i} ≥ 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 ≤ i ≤ ℓ. Let k = |{i : u_{i} = 0}|. Then there is a frame of type (mt)^{g}(2u)^{1}, where u = ∑ u_{i}, having k(m − 1) HOP transversals with respect to the hole of size 2u.

2.4 Starter-adder Constructions

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 frame starter in G\H is a set of unordered pairs S = {{s_{i}, t_{i}} : 1 ≤ i ≤ (g − h)/2} which satisfies the following two properties:

1. {s_{i} : 1 ≤ i ≤ (g − h)/2} ∪ {t_{i} : 1 ≤ i ≤ (g − h)/2} = G\H

2. {±(s_{i} − t_{i}) : 1 ≤ i ≤ (g − h)/2} = G\H.

An adder for S is an injection A : S → G\H such that

{s_{i} + A(s_{i}, t_{i}) : 1 ≤ i ≤ (g − h)/2} ∪ {t_{i} + A(s_{i}, t_{i}) : 1 ≤ i ≤ (g − h)/2} = G\H.

It is well-known that a frame starter and adder in G\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.

Lemma 2.1 Suppose there exists a frame starter and adder in G\H, where |G| = g and |H| = h. Then there exists a frame of type h^{g/h} having (g − h)/2 disjoint CO transversals.

Proof. Each of the (g − h)/2 pairs in the frame starter gives rise to a CO transversal in the resulting frame.

In the case where H = {0}, a frame starter S is termed a starter. If the mapping A defined by A(s_{i}, t_{i}) = −(s_{i} + t_{i}) is an adder, then S is called a 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 [16]. 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−intransitive frame starter-adder (or IFSA) in G\H is a quadruple (S, C, R, A), where

S = {{s_{i}, t_{i}} : 1 ≤ i ≤ (g − h)/2 − 2k} ∪ {u_{i} : 1 ≤ i ≤ 2k}

C = {{p_{i}, q_{i}} : 1 ≤ i ≤ k}

R = {{p′_{i}, q′_{i}} : 1 ≤ i ≤ k}

A : S → G\H is an injection that satisfies the following properties:

(i) {s_{i}} ∪ {t_{i}} ∪ {p_{i}} ∪ {q_{i}} = G\H
(ii) {s_{i} + A(s_{i}, t_{i})} ∪ {t_{i} + A(s_{i}, t_{i})} ∪ {p_{i} + A(u_{i})} ∪ {p′_{i}} ∪ {q′_{i}} = G\H
(ii) {±(s_{i} − t_{i})} ∪ {±(p_{i} − q_{i})} ∪ {±(p′_{i} − q′_{i})} = G\H
(iv) Any element p_{i} − q_{i} or p′_{i} − q′_{i} has even order, 1 ≤ i ≤ k.

By [16, Lemma 3.3], a 2k−IFSA in G\H can be used to construct a frame of type h^{g/h}(2k)^{1}. For each {u_{i}} ∈ S, we create a pair {∞_{i}, u_{i}}, and the final frame contains a hole of size 2k on the infinite elements.

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

3 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 ≥ 4, a frame of type t^{4} exists if t is even, t ≠ 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 ≡ 2 mod 4, t ≥ 6, t ≠ 14.

Here is the main recursive construction.

Theorem 3.1 Suppose there is a frame of type {s_{1}, …, s_{n}}, and for 1 ≤ i ≤ n, suppose there is a frame of type s_{i}^{4}. Then there is a frame of type t^{4}, where t = ∑_{i=1}^{n} s_{i}.

Proof. From the frame of type {s_{1}, …, s_{n}}, we obtain a double frame using Construction 2.7 with m = 4. Then use Construction 2.4, filling in frames of types s_{i}^{4}, 1 ≤ i ≤ n. We obtain a frame of type t^{4}.

Lemma 3.2 Suppose t ≡ 2 mod 4, 6 ≤ t ≤ 46, t ≠ 14. Then there is a frame of type t^{4}.

Proof. Frames of types 6^{4} and 10^{4} were constructed in [7]. These two frames then give rise to frames of types 18^{4} and 30^{4} using Construction 2.6 with m = 3.

Next, from frames of types 4^{4}6^{1} [16], 4^{5}6^{1}, 4^{1}6^{5}, and 4^{2}6^{5} [7], we obtain frames of types 22^{4}, 26^{4}, 34^{4} and 38^{4} by applying Theorem 3.1. From a frame of type 6^{7} (Theorem 1.2) 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 Z_{10}\{0, 5} (see [18]). The resulting frame of type 2^{5} has four disjoint CO transversals. Apply Construction 2.9 with ℓ = 3, m = 4, and u_{i} = 1 (i = 1, 2, 3). We get a frame of type 8^{5}6^{1}. Then apply Theorem 3.1 to get a frame of type 46^{4}.

Lemma 3.3 Suppose t ≡ 2 mod 4, 50 ≤ t ≤ 206. Then there is a frame of type t^{4}.

Proof. For 11 ≤ g ≤ 49, g odd, there is a starter and adder in Z_{g}. So for these values of g, there is a frame of type 1^{g} having 3 or 4 disjoint CO transversals (Lemma 2.1). Then apply Construction 2.9 with ℓ = 3 or ℓ = 4, m = 4, and u_{i} = 1 (1 ≤ i ≤ ℓ). We obtain frames of type 4^{g}6^{1} and 4^{g}10^{1} for these values of g. Then apply Theorem 3.1.

We now prove the main result of this section.

Theorem 3.4 Suppose t ≡ 2 mod 4, t ≥ 6, t ≠ 14. Then there is a frame of type t^{4}.

Proof. The cases t ≤ 206 have already been done, so we can assume t ≥ 210. We can write t = 4g + a, where a ∈ {6, 10, 18, 22, 26, 38}, g ≡ 1 mod 6, g ≥ 43. For such g, there is a starter and adder in Z_{g} (see [13]). This starter has a/2 disjoint CO transversals (Lemma 2.1). Apply Construction 2.9 with ℓ = a/2, m = 4, and u_{i} = 1 (1 ≤ i ≤ ℓ), and then apply Theorem 3.1.

Theorem 1.5 is now an immediate consequence of Theorems 1.2 and 3.4.

4 Incomplete Room Squares

In this section, we construct all but one of the incomplete Room squares listed as unknown in Theorem 1.3. The following IRS are obtained using the hill-climbing algorithm described in [7]. They are presented in the research report [8].

Lemma 4.1 There exists an (n, s)−IRS if

(n, s) ∈ {(55, 17), (59, 17), (61, 17), (63, 17), (63, 19), (65, 19), (83, 25)}.

The following lemma was given in [19, Lemma 4.4].

Lemma 4.2 Suppose there exists a starter and adder in Z_{g}. Suppose 0 ≤ u ≤ 3(g − 1)/2 and 0 ≤ k ≤ 7((g − 1)/2 − ⌈(u/3)⌉). Further, suppose there is a (6u + 2k + 11, 2u + 3)−IRS. Then there is a (24g + 6u + 2k + 11, 8g + 2u + 3)−IRS.

Lemma 4.3 There exists an (n, s)−IRS if

(n, s) ∈ {(271, 89), (275, 89), (277, 89), (319, 105), (325, 105), (327, 105), (367, 121)}.

Proof. These IRS are constructed by using Lemma 4.2. The details are given in Table 1. These applications make use of the IRS constructed in Lemma 4.1.

Table 1: Construction of IRS

\begin{matrix}g & u & k & (6u + 2k + 11, 2u + 3) & (24g + 6u + 2k + 11, 8g + 2u + 3) \\ 9 & 7 & 1 & (55, 17) & (271, 89) \\ 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{matrix}

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

Lemma 4.4 Suppose there is a frame of type t_{1}^{g}t_{2}^{1} having ℓ disjoint HOP transversals with respect to the hole of size t_{2}, where t_{1} ≥ 6 is even, t_{1} ≠ 14. Let 0 ≤ u ≤ ℓ. 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_{1}g + t_{2} + 1.

Proof. Start with the frame of type t_{1}^{g}t_{2}^{1} and apply Construction 2.11 with m = 3 and u_{i} = 0 or 1, 1 ≤ i ≤ ℓ. We obtain an I−frame of type (3t_{1}, t_{1})^{g}(3t_{2} + 2u, t_{2})^{1}, where u = ∑_{i=1}^{ℓ} u_{i}. Now adjoin t_{1} new points and apply Construction 2.3 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 2.2 with a = 1.

Corollary 4.5 (i) Suppose there is a frame of type 6^{g}t^{1} having ℓ 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 ≤ u ≤ ℓ. Then there exists a (3v + 2u + 4, v)−IRS, where v = 6g + t + 1.

(ii) Suppose there is a frame of type 8^{g}t^{1} having ℓ 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 ≤ u ≤ ℓ. Then there exists a (3v +2u+6, v)−IRS, where v = 8g +t+1.

Here is a further specialization of Corollary 4.5.

Corollary 4.6 (i) Suppose there is a frame of type 6^{g}. Then there exists a (3v + 4, v)−IRS, where v = 6g + 1.

(ii) Suppose there is a frame of type 8^{g}. Then there exists a (3v + 6, v)−IRS, where v = 8g + 1.

Proof. Take t = 0 in Corollary 4.5; then ℓ = 0 and u = 0.

Table 2: Construction of IRS

\begin{matrix}t & u & (3t + 2u + 7, t + 1) & (3t + 2u + 79, t + 25) \\ 2 & 0 & (13, 3) & (85, 27) \\ 2 & 2 & (17, 3) & (89, 27) \\ 2 & 4 & (21, 3) & (93, 27) \\ 2 & 5 & (23, 3) & (95, 27) \\ 4 & 0 & (19, 5) & (91, 29) \\ 4 & 2 & (23, 5) & (95, 29) \\ 4 & 3 & (25, 5) & (97, 29) \\ 6 & 1 & (27, 7) & (99, 31) \end{matrix}

Lemma 4.7 There exists an (n, s)−IRS if

(n, s) ∈ {(79, 25), (97, 31), (115, 37), (151, 49), (169, 55)}.

Proof. Apply Corollary 4.6 (i) with g = 4, 5, 6, 8 and 9. Lemma 4.8 There exists an (n, s)−IRS if (n, s) ∈ {(129, 41), (153, 49)}. Proof. Apply Corollary 4.6 (ii) with g = 5 and 6. Lemma 4.9 There exists an (n, s)−IRS if (n, s) ∈ {(109, 35), (127, 41)}. Proof. Apply Corollary 4.5 (i) with g ∈ {5, 6}, t = 4 and ℓ = u = 0. Frames of types 6^{5}4^{1} and 6^{6}4^{1} are constructed in [7]. Lemma 4.10 Suppose 1 ≤ k ≤ 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. Proof. The frames are obtained from intransitive starter-adders presented in the Appendix. Lemma 4.11 There exists an (n, s)−IRS if

(n, s) ∈ {(85, 27), (89, 27), (93, 27), (95, 27), (91, 29), (95, 29), (97, 29), (99, 31)}. Proof. Apply Corollary 4.5 (i) with g = 4 and ℓ = 9 − t, where the values of t and u are given in Table 2. The required input frames of type 6^{4}t^{1} come from Lemma 4.10.

Lemma 4.12 There exists a (111, 35)−IRS.

Proof. Apply Corollary 4.5 (ii) with g = 4, t = 2 and ℓ = 0. We use a frame of type 8^{4}2^{1}, which is obtained from an intransitive starter-adder presented in the Appendix.

Lemma 4.13 There exists a (171, 55)−IRS and a (173, 55)−IRS.

Proof. Apply Corollary 4.5 (ii) with g = 6, t = 6 and ℓ = 12. We use a frame of type 8^{6}6^{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.

Lemma 4.14 There exists an (n, s)−IRS if (n, s) ∈ {(149, 47), (151, 47), (153, 47)}.

Proof. We first apply Construction 2.12 with t = 2, g = 5, ℓ = 4, u_{i} = 1 for 1 ≤ i ≤ 4, m = 4. The ingredients required are as follows: a frame of type 2^{5} having four CO transversals (see the proof of Lemma 3.2); a SOLSSOM(4) in which the SOM is unipotent (Figure 2); and a partitionable ISOLS(5; 1) (Figure 1). The result is a frame of type 8^{5}6^{1} having three HOP transversals with respect to the hole of size six.

Then apply Corollary 4.5 (ii) with g = 5, t = 6 and ℓ = 3 to obtain the desired IRS.

Lemma 4.15 There exists an (n, s)−IRS if (n, s) ∈ {(139, 45), (157, 51), (175, 57)}.

Proof. These IRS are obtained by apllication of Corollary 4.5 (i).

To construct a (139, 45)−IRS, we begin with a frame of type 2^{7} that has an HOP transversal [17, Figure 1]. Then apply Construction 2.10 with t_{1} = t_{2} = 2, g = 6, ℓ = 1, u_{i} = 1 and m = 3. We obtain a frame of type 6^{6}8^{1}. Finally, apply Corollary 4.5 (i) with g = 6, t = 8, u = ℓ = 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 [17, 18]). Apply Construction 2.8 with ℓ = 1, u_{1} = 1 and m = 3. This yields a frame of type 6^{8}2^{1} (6^{9}2^{1}, resp.). Finally, apply Corollary 4.5 (i) with g = 8 (g = 9, resp.), t = 2, and u = ℓ = 0.

Lemma 4.16 There exists an (n, s)−IRS if

(n, s) ∈ {(61, 19), (81, 25), (143, 45), (145, 47)}.

Proof. We begin with a frame of type 2^{7}6^{1}, which is given in [8]. Apply Construction 2.6 with m = 3, 4 and 7, obtaining frames of types 6^{7}18^{1}, 8^{7}24^{1} and 14^{7}42^{1}. Then apply Construction 2.1 to the first two frames with a = 1, and apply it to the last frame with a = 3, 5, producing the desired IRS.

Theorem 1.6 is now an immediate consequence of Theorem 1.3 and Lemmas 4.1, 4.3, 4.7–4.9, and 4.11–4.16.

Table 3: Types 2^{u}t^{1} for which a frame has not been constructed

\begin{matrix}t & u \\ 6 & 7 – 29 \\ 8 & 9 – 29 \\ 10 & 11 – 34 \\ 12 & 13 – 34 \\ 14 & 15 – 39 \\ 16 & 17 – 39 \\ 18 & 19 – 44 \end{matrix}

5 Frames of Type 2^{u}t^{1}

In this section, we study the spectrum of frames of type 2^{u}t^{1}. Recall that t must be even and u ≥ t + 1 for such a frame to exist. In view of Theorem 1.4, we need only consider the cases where 6 ≤ t ≤ 18. For these values of u, there exist frames of type 2^{u}t^{1} if u ≥ 5 ⌈\frac{t}{4}⌉ + 20.

We begin by listing in Table 3 the pairs (t, u) that we need to eliminate.

Lemma 5.1 There exists a frame of type 2^{u}t^{1} for all pairs (t, u) such that t is even, 10 ≤ t ≤ 18 and 25 ≤ u ≤ 44.

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 2.5, filling in frames of type 2^{a}4^{6−b} [5]. The resulting frame has order 2u+t and has a hole of size t. Then apply Construction 2.1 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 ≤ n ≤ 9).

Lemma 5.2 There exist frames of type 2^{28}6^{1} and 2^{29}6^{1}.

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^{7}6^{1}, which is given in the research report [8].

Lemma 5.3 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}.

Proof. In each case, we start with a frame of type t^{u}, and adjoin a new points, applying Construction 2.1. 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 4.

Table 4: Frames of type 2^{u}t^{1}

\begin{matrix}t & u & a & 2^{t/2}a^{1} & 2^{t(u−1)/2}(t + a)^{1} \\ 8 & 4 & 2 & 2^{5} & 2^{12}10^{1} \\ 8 & 5 & 2 & 2^{5} & 2^{16}10^{1} \\ 10 & 4 & 2 & 2^{6} & 2^{15}12^{1} \\ 10 & 4 & 4 & 2^{5}4^{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^{5}4^{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^{6}4^{1} & 2^{18}16^{1} \\ 16 & 4 & 2 & 2^{9} & 2^{24}18^{1} \end{matrix}

Lemma 5.4 There exists a frame of type 2^{24}t^{1} for t even, 6 ≤ t ≤ 16.

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 2.5, filling in frames of type 3^{5} and 3^{4}1^{1} [7]. The resulting frame has type 12^{4}(12 − 2b)^{1}, 0 ≤ b ≤ 4. Then apply Construction 2.1 with a = 0, 2 or 4. The holes can be filled in with frames of type 2^{6}a^{1}, producing a frame of type 2^{24}(12 − 2b + a)^{1}. This yields frames of the desired types.

Lemma 5.5 There exist frames of types 2^{25}6^{1} and 2^{25}8^{1}.

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 2.5, filling in frames of type 2^{5} and 2^{6}. We get frames of types 10^{5}6^{1} and 10^{5}8^{1}. Then apply Construction 2.1 with a = 0, filling in the size 10 holes with frames of type 2^{5}.

Lemma 5.6 There exist frames of types 2^{21}10^{1} and 2^{22}10^{1}.

Proof. Give weight two to every point of a TD(5, 5). Apply Construction 2.5, 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^{5}a^{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}.

Lemma 5.7 There exist frames of types 2^{u}16^{1} for u = 17, 21, 22 and 23.

Proof. There is a frame starter and adder in (Z_{4} × Z_{4}) \{(0, 0), (0, 2), (2, 0), (2, 2)} (see [16, Lemma 5.1]). This gives rise to a frame of type 4^{4} having six disjoint COP transversals. Apply Construction 2.11 with t_{1} = 4, t_{2} = 0, g = 4, ℓ = 6, u_{i} = 0 or 1 (1 ≤ i ≤ 6) and m = 3. We get an I−frame of type (12, 4)^{4}(2u, 0)^{1}, where 0 ≤ u ≤ 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^{5}4^{1}. The size 2u hole is filled in with a frame of type 2^{u+1}. This yields the four desired frames.

Lemma 5.8 There exist frames of types 2^{u}18^{1} for 20 ≤ u ≤ 23.

Proof. There is a frame starter and adder in ((Z_{4} × Z_{4}) \{(0, 0), (0, 2), (2, 0), (2, 2)})∪ {∞_{1}, ∞_{2}} (see [16, Figure 5.2]). This gives rise to a frame of type 4^{4}2^{1} having four disjoint HOP transversals with respect to the hole of size 2. Apply Construction 2.11 with t_{1} = 4, t_{2} = 2, g = 4, ℓ = 4, u_{i} = 0 or 1 (1 ≤ i ≤ 4) and m = 3. We get an I−frame of type (12, 4)^{4}(2u + 6, 2)^{1}, where 0 ≤ u ≤ 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^{5}4^{1}. The size 2u + 6 hole is filled in with a frame of type 2^{u+4}. This yields the four desired frames.

The following was shown in [10, Example 2.3].

Lemma 5.9 There exists a frame of type 2^{8}6^{1}.

The remaining frames of type 2^{u}t^{1}, except type 2^{19}18^{1}, are presented in the research report [8].

6 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 [4, 7]), though we have expended condsiderable computer time searching for them.

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.

References

[1] J. H. Dinitz and E. R. Lamken. Uniform Room frames with five holes. J. Combin. Designs 1 (1993), 323–328.

[2] J. H. Dinitz and E. R. Lamken. Howell designs with subdesigns. J. Combin. Theory A 65 (1994), 268–301.

[3] J. H. Dinitz and D. R. Stinson. Further results on frames. Ars Combinatoria 11 (1981), 275–288.

[4] J. H. Dinitz and D. R. Stinson. A hill-climbing algorithm for the construction of one-factorizations and Room squares. SIAM J. on Algebraic and Discrete Methods 8 (1987), 430–438.

[5] J. H. Dinitz and D. R. Stinson. On the existence of Room squares with subsquares. Contemporary Mathematics 111 (1990), 73–91.

[6] J. H. Dinitz and D. R. Stinson. Room squares and related designs. In “Contemporary Design Theory: A Collection of Surveys”, John Wiley & Sons, 1992, pp. 137–204.

[7] J. H. Dinitz and D. R. Stinson. A few more Room frames. In “Graphs, Matrices and Designs”, Marcel Dekker, 1993, pp. 133–146.

[8] J. H. Dinitz, D. R. Stinson and L. Zhu. Some new frames. Research Report (available in the “Comments” file for this paper).

[9] B. Du and L. Zhu. The existence of incomplete Room squares. J. Combin. Math. Combin. Comput. 14 (1993), 183–192.

[10] G. Ge. On the existence of Room frames of type 2^{n}u^{1}. J. Statist. Plan. Infer., to appear.

[11] G. Ge and L. Zhu. On the existence of Room frames of type t^{u} for u = 4 and 5. J. Combin. Designs 1 (1993), 183–191.

[12] G. Ge and L. Zhu. Existence of Room frames of type 2^{n}u^{1}. J. Combin. Math. Combin. Comput., to appear.

[13] J. D. Horton. Orthogonal starters in finite abelian groups. Discrete Math. 79 (1989/90), 265–278.

[14] E. R. Lamken and S. A. Vanstone. The existence of skew Howell designs of side 2n and order 2n + 2. J. Combin. Theory A 54 (1980), 20–40.

[15] R. C. Mullin and W. D. Wallis. The existence of Room squares. Aequationes Math. 13 (1975), 1–7.

[16] D. R. Stinson. Some constructions for frames, Room squares, and subsquares. Ars Combinatoria 12 (1981), 229–267.

[17] D. R. Stinson. On the existence of skew Room frames of type 2^{n}. Ars Combinatoria 24 (1987), 115–128.

[18] D. R. Stinson and W. D. Wallis. Some designs used in constructing skew Room squares. Ann. Discrete Math. 8 (1980), 171–175.

[19] D. R. Stinson and L. Zhu. Towards the spectrum of Room squares with subsquares. J. Combin. Theory A 63 (1993), 129–142.

Appendix: Some Intransitive Starter-adders

In this Appendix, we construct some new frames using the method of intransitive starter-adders described in Section 2.4. 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}^{u}t_{2} from a t_{2}−IFSA in

(Z_{t_{1}u}\{iu : 0 ≤ i ≤ t_{1} − 1}) ∪ {∞_{j} : 1 ≤ j ≤ t_{2}}.

type 6^{4}2^{1}

starter adder starter
{7, ∞_{1}}  10  {17, ∞_{1}}
{23, ∞_{2}}  11  {10, ∞_{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}

{10, 21} {11, 21}

type 6^{4}4^{1}
starter adder starter
{15, ∞_{1}}  23  {14, ∞_{1}}
{5, ∞_{2}}  21  {2, ∞_{2}}
{6, ∞_{3}}  17  {23, ∞_{3}}
{10, ∞_{4}}  15  {1, ∞_{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}

{3, 14} {2, 9}

{6, 9}
{7, 22}

type 6^{4}6^{1}

starter adder starter
{2, ∞_{1}}  1  {3, ∞_{1}}
{9, ∞_{2}}  2  {11, ∞_{2}}
{18, ∞_{3}}  5  {23, ∞_{3}}
{1, ∞_{4}}  13  {14, ∞_{4}}
{19, ∞_{5}}  18  {13, ∞_{5}}
{11, ∞_{6}}  19  {6, ∞_{6}}
{10, 13}  21  {7, 10}
{7, 17}  22  {5, 15}
{3, 22}  23  {2, 21}

{5, 23} {6, 21} {14, 15}

{1, 18} {9, 22} {17, 19}

type 8^{4}2^{1}
starter adder starter
{9, ∞_{1}}  9  {18, ∞_{1}}
{31, ∞_{2}}  10  {9, ∞_{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}

{7, 22}

{13, 31}

type 8^{6}6^{1}
starter adder starter
{2, ∞_{1}}  5  {7, ∞_{1}}
{8, ∞_{2}}  13  {21, ∞_{2}}
{15, ∞_{3}}  29  {44, ∞_{3}}
{26, ∞_{4}}  7  {33, ∞_{4}}
{35, ∞_{5}}  3  {38, ∞_{5}}
{41, ∞_{6}}  8  {1, ∞_{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}

{14, 1} {4, 7} {25, 3}

{2, 17}
{45, 46}
{47, 28}