The Nonexistence of 4–(12,6,6) Designs

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

Abstract.

With the help of computer algorithms we prove that there are no 4−(12, 6, 6) designs, thereby answering the last open existence question in design theory for at most 12 points. We also enumerate three families of related designs, namely the 10977 simple 3−(10, 4, 3) designs, the 67 simple 4−(11, 5, 3) designs, and the 23 simple 5−(12, 6, 3) designs. Finally, we complete the census of all possible partitions of 6-sets on 12 points into 5−(12, 6, λ) designs and of 5-sets on 11 points into 4−(11, 5, λ) designs.

1. Introduction.

A t−(v, k, λ) design is a pair (X, D) where X is a v-element set of points and D is a multiset of k-element subsets of X, called blocks, such that for all T ⊆ X, |T | = t, |{K ∈ D : T ⊆ K}| = λ. A design is called simple if it has no repeated blocks. For v ≤ 12, 4−(12, 6, 6) was the only set of parameters for which design existence was unsettled before this work. The recent paper by Kreher, de Caen, Hobart, Kramer and Radziszowski [9] contains much information about the properties of this and related designs, in particular it notes that 4−(12, 6, λ) designs exist for the arithmetically feasible adjacent λ’s, namely 4 and 8, with an unknown case at λ = 6. Our result that no 4−(12, 6, 6) design exists is the first known example where such a hole of nonexistence appears as λ is varied with the other parameters held fixed. The nonexistence of 4−(12, 6, 6) designs was firmly established using three independent methods, many important steps of which were performed in duplicate.

The family of simple t−(t + 7, t + 1, λ) designs is perhaps one of the most investigated parameter situations in design theory [1,2,4,5,7,9,13], with particular attention given to the well known Witt designs with λ = 1. For λ = 2 all such simple designs were described in [13]. The census of this family for λ = 3 is completed here. The study of the latter is included in this work since all the simple t−(t + 7, t + 1, 3) designs for t ≥ 4 are required by one of our proofs of the nonexistence of 4−(12, 6, 6) designs. Table 1 below summarizes the number of nonisomorphic simple t−(t+7, t+1, λ) designs for all t and λ ≤ 3 (for λ ≥ 4 such designs are complements of those with λ ≤ 3). This table completes Table I in [13], the new entries being those with λ = 3 and 3 ≤ t ≤ 5.

\begin{matrix}t & λ = 1 & λ = 2 & λ = 3 \\ 1 & 1 & 3 & 6 \\ 2 & 1 & 13 & 332 \\ 3 & 1 & 27 & 10977 \\ 4 & 1 & 1 & 67 \\ 5 & 1 & 1 & 23 \end{matrix}

Table 1. The number of nonisomorphic simple t−(t + 7, t + 1, λ) designs

Having completed the enumeration of all simple t−(t + 7, t + 1, λ) designs, we could not resist the temptation to answer the remaining open questions concerning their resolvabilities. This problem was studied originally by Kramer and Mesner in [7], who showed that there are at most two disjoint Steiner systems S(5,6,12). Other possible resolvabilities within this family were discussed in [13]. In Section 4 we report our computation completing the census of all possible resolvabilities for interesting t, namely all possible partitions of 6-sets on 12 points into 5−(12, 6, λ) designs and of 5-sets on 11 points into 4−(11, 5, λ) designs.

2. Three Towers of Designs.

For 8 ≤ v ≤ 12, let D_{v}, A_{v} and B_{v} denote any p−(v, s, 6), q−(v, s, 3) and p−(v, q, 4) design, respectively, where p = v − 8, q = v − 7 and s = v − 6. Table 2 gives the number of blocks in these designs in all cases. All such designs are known to exist [3] except D_{12}, i.e. 4−(12, 6, 6). The counts of designs A_{v} appear in the last column of Table 1, and the main goal of this paper is to disprove the existence of D_{12}. Note that the point derived design from D_{v} is a design D_{v−1}, and similarly for A_{v} and B_{v}. In the sequel let \overline{D}_{12} denote the blockwise complement of D_{12}. For all designs we assume a fixed set of points X = {0, 1, …, 11}, or its subset of proper order, and also we will identify designs with their collections of blocks.

v = 8 v = 9 v = 10 v = 11 v = 12
D_{v}  6  18  45  99  198
A_{v}  12  36  90  198  396
B_{v}  4  18  60  165  396

Table 2. The number of blocks in D_{v}, A_{v} and B_{v} designs

The following theorem contains a condensation of some results obtained in [9], which establish relationships between our three towers of designs.

Theorem 1 [9].

(a) Any 4−(12, 6, 6) design must be simple.

(b) For any D_{12}, \overline{D}_{12} is also a 4−(12, 6, 6) design.

(c) D_{12} ∪ \overline{D}_{12} is a simple A_{12} design.

(d) D_{12} ∩ \overline{D}_{12} = ∅; equivalently, D_{12} has no disjoint blocks.

(e) Each 5-set is covered by one or two blocks of D_{12}.

(f) In A_{12}, if S is a block then \overline{S} is also a block.

(g) Each 7-set contains exactly 3 blocks of A_{12}.

(h) The 5-sets covered by one block of D_{12} form a B_{12}.

(i) The 5-sets covered by two blocks of D_{12} form a B_{12}.

(j) Each block of D_{12} intersects 0, 8, 50, 80, 55, 4 other blocks in 0, 1, …, 5 points, respectively.

Some additional properties of A_{v} designs, formulated in Theorem 2 below, were used in the computations.

Theorem 2. Let A_{12} be any simple 5−(12, 6, 3) design. Then

(a) No k-ly derived design of A_{12} (k = 0, 1, 2, 3) can have a (7 − k)-set containing more than 3 blocks.

(b) If A_{10} is a doubly derived design from A_{12}, then any 5-set of A_{10} contains 1, 2, or 3 blocks.

Proof. Since we consider only simple designs, properties (a) and (b) follow immediately from Theorem 1 (g).

3. Algorithms.

The success of our study was considerably facilitated by the use of efficient programs for the canonical labelling of designs. The program nauty written by the first author [11] can perform rapid canonical labelling of arbitrary graphs, and so can be applied to the bipartite point-block incidence graphs of designs. However, this approach is not very efficient, as the graphs are quite large (v + b vertices) and labellings are treated as permutations of the points and blocks together. In fact, it suffices to treat labellings of the points only, as an ordering of the points implies an ordering of the blocks apart from the interchange of equal blocks.

Accordingly, a version of nauty was prepared that treats designs (X, D) as hypergraphs with vertex set X and edge set D. Both vertices and edges can be coloured, the latter to enable direct processing of the partitionings we will describe in Section 4. Automorphisms and labellings appear as permutations of X only. Only about 5% of the code for nauty needed to be replaced, but the result was an improvement of about one order of magnitude in processing efficiency.

Typical execution times for computing automorphism groups and canonical labellings are 0.5 seconds for 3−(10, 4, 2) designs, 1.6 seconds for 3−(10, 4, 3) designs, 20 seconds for 4−(11, 5, 3) designs and 520 seconds for 5−(12, 6, 3) designs. These times are in fact unnecessarily long, as the program is tuned not for completed designs but for partial designs induced by some subset of the points. In this case the program is usually very much faster, for example 0.011 seconds for six points of a 3−(10, 4, 3) design. All the computer times given in this paper refer to a Sun Microsystems Sparcstation One computer (approximately 12 mips).

There are a very large number of designs D_{10}. This lead us to avoid the most natural approach of enumerating D_{12}’s by straightforward extensions D_{i} → D_{i+1}, for i = 8, …, 11. Instead we took two alternative approaches, one similar to the algorithms described by Ivanov [6], and the other one using design extensions A_{i} → A_{i+1}, for i = 8, …, 11 and the relationship between the A_{v}-tower and D_{v}-tower of designs.

Let S be a t−(v, k, λ) design with b blocks. If one sees S as a b×v (0,1)-matrix M with M[i, j] = 1 if and only if block i contains point j, then the core of our two approaches lies in finding a labelling in which column-by-column or row-by-row, respectively, construction of M is efficient, and limits the combinatorial explosion in the number of intermediate configurations. In our experience both methods may work well after a proper combinatorial study of the design S is performed. In the case of D_{v} and A_{v} designs such a detailed study has been done in [9]. The bulk of the current work consisted of the choice of properties to be implemented, the choice of appropriate methods for the different computational paths, and finally implementation, tuning of programs and verification of results.

ALG1. Column-by-column construction. Let S[n] stand for the configuration of partial blocks of S corresponding to the first n columns of matrix M. The set of feasible (n+1)-th columns are the 0-1 solutions of a set of linear equations that express the basic design properties. In addition, there may be further equations or inequalities derived from theory such as that in Theorem 1. If S[n] has many equal rows, there can be many solutions which only differ by the interchange of those rows. Such equivalent solutions can be avoided by replacing the 0-1 variables for each set of equal rows by an integer variable equal to their sum.

Overall isomorph rejection can be handled by several different methods. One is to simply generate all feasible extensions and reject isomorphs using nauty. The other employs nauty in a quite different way. Suppose S[n + 1] is constructed by adjoining column n+1 to S[n]. Application of nauty provides the orbits of the automorphism group of S[n + 1] and also a canonical labelling of the columns. S[n + 1] is then rejected if column n + 1 is not in the same orbit as the column whose canonical label is “1”. Isomorph rejection is then carried out only within the matrices derived from each particular S[n]. It is not hard to show [12] that each isomorphism class is represented exactly once in the output.

ALG2. Row-by-row construction. By using a suitable labelling of the points, this approach is reduced to consecutive extension of (s−1)-designs S_{s−1} to s-designs S_{s}, for s = 1, …, t. All extensions of a single (s−1)- design can be obtained by solving an appropriate system of integer equations (possibly also inequalities, if known). Each design extension adds |S_{s}| − |S_{s−1}| rows to the matrix M.

4. Constructive Results.

Using both methods (ALG1) and (ALG2) from Section 3, we have obtained the following enumeration results. The computations will be described in more detail in Section 5.

Theorem 3.

(a) There are exactly 10977 nonisomorphic simple 3−(10, 4, 3) designs. Of these, 1685 satisfy condition (b) of Theorem 2, and 248 of the latter extend to a simple 4−(11, 5, 3) design.

(b) There are exactly 67 nonisomorphic simple 4−(11, 5, 3) designs. Of these, 28 are rigid, 6 have groups of order 2, 14 of order 3, 6 of order 4, 11 of order 8, and one each of orders 12 and 24. None of these designs is point transitive.

(c) There are exactly 23 nonisomorphic simple 5−(12, 6, 3) designs. Of these, none is rigid, 3 have groups of order 2, 2 of order 3, 2 of order 9, 4 of order 12, 2 of order 16, 3 of order 36, 2 of order 48, and one each of orders 6, 24, 32, 144 and 288. Exactly seven of these designs are point transitive.

Observe that by Alltop’s extension theorem every A_{11} extends uniquely to an A_{12}, hence given all A_{12}’s one can easily recover all A_{11}’s. Several A_{12} designs have been described in [9], hence here we only note that we found 10 more, including one with the largest automorphism group of order 288. The latter design is described in full in the sequel as a part of a partition of all 6-sets on 12 points into 5-designs. The interested reader is encouraged to request electronic copies of some or all designs from Theorem 3 from the authors.

Some particularly beautiful configurations of sets can be obtained by partitioning all k-subsets of a v-set into designs. Kramer and Mesner [7] proved that there are no three mutually disjoint Steiner systems S(5, 6, 12). The computations in [13] showed that there is a unique simple 5−(12, 6, 2) design, which is formed by two disjoint copies of S(5, 6, 12). As observed in [13], this implies that the only possible partitions of all 6-sets on 12 points into nonresolvable 5−(12, 6, λ) designs are of type (1+1+5) or (1+3+3), where the type lists the λ’s of the participating resolvent designs. In particular, the latter implies that there is no resolvable simple 5−(12, 6, 3) design. A very detailed study of type (1+1+5) partition can be found in [7]. Before the current work no partition of type (1+3+3) was known.

Please note that all the remarks of the preceding paragraph are equally valid for partitioning the 5-sets on 11 points into 4−(11, 5, λ) designs.

By analyzing the designs from Theorem 3(b) and 3(c) we have been able to construct all such nonisomorphic partitions on 11 and 12 points, and we summarize them in the next theorem. By an automorphism of a type (1+3+3) partition into designs we understand a permutation of points which is an automorphism of the Steiner resolvent, and is an automorphism of two other resolvents or is an isomorphism between them. The resolvability claims below are consequences of Theorem 3, the computations, and the remarks above.

Theorem 4.

(a) There are exactly 7 nonisomorphic partitions of all 5-sets on 11 points into 4−(11, 5, λ) designs of type (1 + 3 + 3). Of these, two are rigid, and the other 5 have 3 automorphisms. In no case is there an automorphism exchanging two resolvents. Nine nonisomorphic 4−(11, 5, 3) designs are resolvents of such partitions; equivalently, 58 of the 67 simple 4−(11, 5, 4) designs are not resolvable.

(b) There are exactly 5 nonisomorphic partitions of all 6-sets on 12 points into 5−(12, 6, λ) designs of type (1 + 3 + 3). Of these, two have 9 automorphisms, and the other 3 have 36 automorphisms and are point transitive. In no case is there an automorphism exchanging two resolvents. Seven nonisomorphic 5−(12, 6, 3) designs are resolvents of such partitions; equivalently, 16 of the 23 simple 5−(12, 6, 4) designs are not resolvable.

Similarly to Theorem 3, every partition from (a) extends uniquely to a partition from (b). Also, given all partitions from (b), one can easily recover all partitions from (a).

Now we will give a full description of a partition of type (1 + 3 + 3). We will call the resolvents R_{1}, R_{2} and R_{3}, respectively.

Define four permutations of {0, 1, …, 11}:

\begin{aligned}g_{1} & = (1 3 5)(2 11 10)(6 8 9) \\ g_{2} & = (0 2 7 1 4 8)(3 10 9 5 11 6) \\ g_{3} & = (4 5 11 8)(6 10 7 9) \\ g_{4} & = (3 5)(4 10)(7 9) \end{aligned}

Resolvent R_{1} is a 5−(12, 6, 1) design. Its automorphism group is G_{1} = ⟨g_{1}, g_{2}, g_{3}⟩, which is a 5-transitive representation of the Matthieu group M_{12} (order 95040). The action on the blocks is transitive. Resolvent R_{2} is a 5−(12, 6, 3) design. Its automorphism group is G_{2} = ⟨g_{1}, g_{2}, g_{4}⟩, which acts transitively and has order 288 (the largest for any 5−(12, 6, 3) design). There are seven orbits of blocks. Resolvent R_{3} is a 5−(12, 6, 3) design. Its automorphism group is G_{3} = ⟨g_{1}, g_{2}⟩, which acts transitively and has order 36. There are eleven orbits of blocks.

In Table 3, we give the lengths and representative members of the actions of group G_{i} on the blocks of R_{i}, for i = 1, 2, 3. Since G_{3} = G_{1} ∩ G_{2} and the three resolvents are nonisomorphic, the full automorphism group of the partition is G_{3}.

5. Computations.

The nonexistence of D_{12} was established by three independent computations, and all the design constructions have been obtained at least twice each, with different implementations.

The following were the major computations for this work: sequences (C1) and (C2) used the point extension algorithm (ALG1), sequence (C3) used the standard design extension algorithm (ALG2), and (C4) used both.

Resolvent  Orbit length  Representative
R_{1}  132  {5, 6, 7, 8, 9, 10}
R_{2}  12  {3, 4, 5, 6, 8, 10}
12  {3, 4, 5, 7, 9, 10}
18  {3, 5, 6, 7, 8, 9}
48  {3, 5, 7, 8, 10, 11}
144  {4, 5, 7, 8, 10, 11}
144  {5, 7, 8, 9, 10, 11}
18  {6, 7, 8, 9, 10, 11}
R_{3}  36  {3, 4, 5, 7, 8, 10}
36  {3, 4, 5, 8, 9, 10}
36  {3, 5, 7, 8, 9, 10}
36  {3, 5, 8, 9, 10, 11}
36  {4, 5, 6, 9, 10, 11}
36  {4, 5, 7, 8, 9, 11}
36  {4, 5, 7, 9, 10, 11}
36  {4, 7, 8, 9, 10, 11}
36  {5, 6, 7, 8, 9, 11}
36  {5, 6, 7, 8, 10, 11}
36  {5, 6, 7, 9, 10, 11}

Table 3. A partition of all 6-sets on 12 points into three 5−(12, 6, λ) designs

(C1) D_{12}[6] → D_{12}[7] → D_{12}[8] → D_{12}[9] → D_{12}[10]. Properties (a), (b), (c), (e), (j) of Theorem 1 were enforced for D_{12}, and property (e) for \overline{D}_{12}. The unique D_{12}[6] containing a full block was used as a starting point. In addition the required number of partial blocks of each size were encoded. It is worth observing that some of these properties are logically redundant, but experiments showed that their explicit inclusion dramatically decreased the execution time. The numbers of partial designs obtained at each level were 1, 13, 28794, 14084, and 3, respectively. None of the three designs D_{12}[10] extended to 11 points.

(C2) A_{12}[6] → A_{12}[7] → ⋯ → A_{12}[12]. Properties (f) and (g) of Theorem 1, and the pattern of blocks sizes within each 7-set were enforced. The starting points were the two possible configurations of six points, one covering a block, the other not. The numbers of partial designs obtained at each level were 2, 1, 6, 232, 2424, 67 and 23, respectively. The value 2424 is reduced to 1685 if property (b) of Theorem 2 is enforced as well. It was checked that the generated A_{12}’s do not split into D_{12} ∪ \overline{D}_{12}.

(C3) A_{8} → A_{9} → A_{10}^{∗} → A_{11} → A_{12}. The designs A_{9} agreed with the results in [5]. Only special A_{10}’s were produced, namely those satisfying Theorem 2(b). The number of designs obtained at each level was 6, 332, 1685, 67 and 23, respectively. Crosschecks with intermediate results of sequences (C1) and (C2) were done. It was checked twice that D_{12} cannot be obtained: firstly by splitting special A_{10}’s into candidates for partial systems D_{12}[10] ∪ \overline{D}_{12}[10] and showing that none can be completed, and secondly by verifying that A_{12}’s do not split into D_{12} ∪ \overline{D}_{12}.

(C4) A_{9} → A_{10}. Dramatic improvement of the programs after (C3) had been completed enabled the full census of all 10977 simple 3−(10, 4, 3) designs A_{10} to be completed in about 100 hours by method (ALG2). In slightly more time, it was repeated by method (ALG1) with identical results. Finally, the special designs A_{10}^{∗} needed by (C3) were extracted from the 10977 and checked against those found before.

In addition, several small testing programs were implemented to crosscheck other intermediate results of different sequences. These programs were based on obvious relationships between designs, and the properties listed in Theorems 1 and 2. For example, 248 out of the 1685 special A_{10}’s produced in sequence (C3) extended to 67 A_{11}’s. After rejecting isomorphs amongst the 11 × 67 point derived designs, we recovered the same set of 248 A_{10}’s. Note that each of the sequences (C1), (C2) and (C3) shows the nonexistence of D_{12} designs. Thus we have:

Theorem 5. 4−(12, 6, 6) designs do not exist.

The partitions of Theorem 4 were obtained as follows. First we produced all simple 4−(11, 5, 4) designs by taking the complements of A_{11}’s. Then using an equation solver we found all possible embeddings of the Steiner system S(4, 5, 11) as a subdesign of each 4−(11, 5, 4). Each such embedding gave an instance of a type (1+3+3) partition. The partitions of Theorem 4(b) were obtained twice: the same way as those of Theorem 4(a) and independently by applying Alltop’s extension theorem to those from Theorem 4(a). As usual, all these computations were performed independently by each of two authors, using distinct programs. The computer time needed to obtain all partitions was negligible.

The total computer time used for all computations was just about 1000 cpu hours, including all repetitions and verification. A single disproof of the existence along path (C3) could be obtained in about 50 cpu hours and along path (C2) in about twice that long. Our computations were completed quickly by using a network of about 120 Sun computers simultaneously.

6. The Next Challenge.

To the best of our knowledge, as reported in [3], only remaining open existence question in design theory for v ≤ 13 is that for 4−(13, 6, 6) designs (286 blocks). For other arithmetically feasible λ’s with the same parameters such designs exist; namely, there are known constructions of simple 4−(13, 6, 12) [8] and simple 4−(13, 6, 18) designs. The latter are actually the simple 5−(13, 6, 4) designs found in [10].

The only design on 14 points whose existence is in question is a 5−(14, 7, 6) design [3]. Note that if a 5−(14, 7, 6) design exists, its derived design is a 4−(13, 6, 6) design, mentioned above. Hence any construction of a simple 5−(14, 7, 6) design or proof of the nonexistence of 4−(13, 6, 6) designs would answer all remaining existence questions for v ≤ 14.

Observe that, using the notation from Section 2, the known 5−(13, 6, 4) and 6−(14, 7, 4) designs [10] can be seen to be B_{13} and B_{14}, respectively. We feel that one can expect a relationship between the unknown tower of designs t−(t + 9, t + 2, 6) and t−(t + 8, t + 1, 4) (= B_{t+8}), to be similar to the relationship between the D_{v} and A_{v} towers studied here.

References.

[1] T. Beth, D. Jungnickel and H. Lenz, Design Theory, Cambridge University Press (1986).

[2] A. E. Brouwer, The t-designs with v < 18, Stichting Math. Centrum ZN 76/77, Amsterdam, August 1977.

[3] Y. M. Chee, C. J. Colbourn and D. L. Kreher, Simple t-Designs with v ≤ 30, Ars Combinatoria, 29 (1990) 193–261.

[4] P. B. Gibbons, Computing Techniques for the Construction and Analysis of Block Designs, Ph.D. thesis, Department of Computer Science, University of Toronto (1976).

[5] J. J. Harms, C. J. Colbourn and A. V. Ivanov, A Census of (9,3,3) Block Designs without Repeated Blocks, Congressus Numerantium, 57 (1987) 147–170.

[6] A. V. Ivanov, Constructive Enumeration of Incidence Systems, Annals of Discrete Math., 26 (1985) 227–246.

[7] E. S. Kramer and D. M. Mesner, Intersections Among Steiner Systems, J. Combinatorial Theory, Series A, 16 (1974) 273–285.

[8] E. S. Kramer and D. M. Mesner, t-Designs on Hypergraphs, Discrete Math, 15 (1976) 263–296.

[9] D. L. Kreher, D. de Caen, S. A. Hobart, E. S. Kramer and S. P. Radziszowski, The Parameters 4−(12, 6, 6) and Related t-Designs, Australasian J. Combinatorics, 7 (1993) 3–20.

[10] D. L. Kreher and S. P. Radziszowski, The Existence of Simple 6−(14, 7, 4) Designs, Journal of Combinatorial Theory, Series A, 43 (1986) 237–243.

[11] B. D. McKay, nauty Users’ Guide (Version 1.5), Technical Report TR-CS-90-02, Computer Science Department, Australian National University, 1990.

[12] B. D. McKay, Isomorphic-free exhaustive generation, to appear.

[13] S. P. Radziszowski, Enumeration of All Simple t−(t + 7, t + 1, 2) Designs, J. Combinatorial Math. and Combinatorial Comput., 12 (1992) 175–178.