NOTE

2–(22,8,4) Designs Have No Blocks of Type 3

Brendan D. McKay  Stanisław P. Radziszowski
Department of Computer Science  Department of Computer Science
Australian National University  Rochester Institute of Technology
Canberra, ACT 0200, Australia  Rochester, NY 14623, USA
bdm@cs.anu.edu.au  spr@cs.rit.edu

Abstract.

Using computer algorithms we show that in any 2−(22, 8, 4) design there are no blocks of type 3, thus leaving as possible only types 1 and 2. Blocks of type 3, i.e. those which intersect two others in one point, are eliminated using the algorithms described in our previous paper. It was perhaps the second largest computation ever performed (after the solution to the RSA129 challenge), requiring more than a century of cpu time.

1. Done.

A design is a pair (X, D) where X is a v-element set of points and D is a multiset of subsets of X, called blocks. A t−(v, k, λ) design is a design (X, D) with |X| = v, such that the blocks have size k and |{K ∈ D : T ⊆ K}| = λ for all T ⊆ X with |T | = t. 2−(22, 8, 4) is the smallest design whose existence is unsettled, despite much work by many authors. For an extensive history of the search for 2-(22,8,4) designs, we encourage the reader to consult the excellent recent survey by van Rees [Rees].

Let D denote any 2-(22,8,4) design. It has b = 33 blocks, and each point belongs to r = 12 blocks. In [HK] it is shown that D may have only four types of blocks with respect to their intersection pattern with other blocks, as shown in Table 1. For each type of block the table gives the number b_{i} of blocks intersecting it in i points, for all possible i.

\begin{matrix}Type & b_{0} & b_{1} & b_{2} & b_{3} & b_{4} \\ 1 & 0 & 0 & 12 & 16 & 4 \\ 2 & 0 & 1 & 9 & 19 & 3 \\ 3 & 0 & 2 & 6 & 22 & 2 \\ 4 & 1 & 0 & 6 & 24 & 1 \end{matrix}

Table 1. The types of blocks in D.

This note is a continuation of the previous paper of the same authors [MR], where we proved, with the help of computer algorithms, that blocks of type 4 are impossible and that no three blocks can pairwise intersect in one point. The latter eliminated some blocks of type 3, leaving only those for which the two blocks intersecting it in one point have two points in common. Here we announce the completion of computations implying that the remaining cases of possible blocks of type 3 have been eliminated.

2. Just Completed.

The algorithms and the computation technique were essentially the same as described in [MR]. First, we derived 53937 nonisomorphic pd-systems for the starting partition [ 2 | 2 | 5 | 5 | 8], where the last 8-cell forms a block B of type 3. Two blocks C and D intersecting B in one point contain one 5-cell each, and a common 2-cell. The other 2-cell is disjoint from B, C, and D. The extender algorithm was run on each of these starters.

During the computations we constructed more than half a million nonisomorphic “near” 2−(22, 8, 4) designs, which are collections of 33 blocks of size 8, hitting each of the 22 points 12 times, each pair of blocks intersecting in 1, 2, 3 or 4 points, and such that at least 227 (out of 231) pairs of points are covered exactly 4 times. Among these near designs 179 are special in that they have 29 (the maximum found) blocks of types 1, 2 or 3.

The computer time needed to complete the task was enormous: 1195534 cpu hours of machines of different architectures and speeds, with the average speed slightly higher than that of SUN Sparcstation 2. We estimate the total effort at about 1500 mips years, or about 130 cpu years of Sparc2. The computations were run from May 1995 to August 1996 on up to 200 workstations simultaneously at the home institutions of the authors in Rochester and Canberra, using the first author’s job distribution system autoson [McKay]. The consistency checks were the same as described in [MR].

3. To Do.

Summarizing the main results of [MR], this note, and the survey by van Rees [Rees], any 2-(22,8,4) design D must have the following properties: there are only blocks of type 1 and 2, there is at least one block of type 1, D contains at least 6 possibly-overlapping 5-tuples of blocks of the 7 special 5-tuples listed in [Rees], any automorphism of D is a 2-group without an 8-cycle or is trivial, and no quadruple of points is covered by more than two blocks.

References.

[HK] N. Hamada and Y. Kobayashi, On the block structure of BIB designs with parameters v = 22, b = 33, r = 12, k = 8, and λ = 4, J. Combinatorial Theory, Ser. A, 24 (1978) 75–83.

[McKay] B. D. McKay, Autoson, a distributed batch system for UNIX workstation networks (Version 1.3), Technical Report TR-CS-96-03, Computer Science Department, Australian National University, 1996

http://cs.anu.edu.au/~bdm/autoson.

[MR] B. D. McKay and S. P. Radziszowski, Towards Deciding the Existence of 2- (22,8,4) Designs, J. Combinatorial Mathematics and Combinatorial Computing, 22 (1996) 211–222.

[Rees] G. H. J. van Rees, (22,33,12,8,4)-BIBD, an Update, in Computational and Constructive Design Theory, ed. W. D. Wallis, Kluwer Academic Publ., 1996, 337–357.