Steiner systems S(2, 4, v) - a survey

              Colin Reid, reidct@math.mcmaster.ca
                  Alex Rosa, rosa@mcmaster.ca

Department of Mathematics and Statistics, McMaster University, Hamilton, Ontario, Canada

Submitted: Jan 21, 2009; Accepted: Jan 25, 2010; Published: Feb 1, 2010 Mathematics Subject Classification: 05B05

Abstract

We survey the basic properties and results on Steiner systems S(2, 4, v), as well as open problems.

1 Introduction

A Steiner system S(t, k, v) is a pair (V, B) where V is a v-element set and B is a family of k-element subsets of V called blocks such that each t-element subset of V is contained in exactly one block. For basic properties and results on Steiner systems, see [51].

By far the most popular and most studied Steiner systems are those with t = 2 and k = 3, called Steiner triple systems (STS). There exists a very extensive literature on STSs (see, eg., [54] and the bibliography therein). Steiner systems with t = 3 and k = 4 are known as Steiner quadruple systems and are commonly abbreviated as SQS; there exist (at least) two extensive surveys on SQSs (see [122], [95]); see also [51]). When t = 2, one often speaks of a Steiner 2-design.

Quite a deal of attention has also been paid to the case of Steiner systems S(2, 4, v), but to the best of our knowledge, no survey of known results and problems on these Steiner 2-designs with block size 4 has been published. It is the purpose of this article to fill this gap by bringing together known results and problems on this quite interesting class of Steiner systems. No “catchy” name appears to be in circulation about Steiner systems S(2, 4, v), as opposed to the case of STSs or SQSs.

2 Existence of Steiner systems S(2, 4, v)

Since every pair of distinct elements of an S(2, 4, v) is contained in a unique block, and each block contains six such pairs, the total number of pairs \binom{v}{2} must be divisible by 6, and thus 12 must divide v(v − 1). Also, any element occurs in a block with three further elements, so the total number of other elements, v − 1, must be divisible by three. These two conditions imply that v ≡ 1 or 4 (mod 12) is necessary for an S(2, 4, v) to exist. Hanani [92] was the first to prove the sufficiency of this condition.

Theorem 2.1. A Steiner system S(2, 4, v) exists if and only if v ≡ 1 or 4 (mod 12).

The system of order 1 (with one element and no blocks) and system of order 4 (with four elements and one block) are trivial systems. All systems of order at least 13 are nontrivial.

In 1939, Bose [15] gave a construction of two infinite classes of S(2, 4, v)s using finite fields (cf. also [91], Theorems 15.3.5 and 15.3.6).

Theorem 2.2. Let v = p^{n} = 12t + 1, p prime, and if α is a primitive root of GF (p^{n}) such that α^{4t} − 1 = α^{q} for some odd q, then the blocks

{0, α^{2i}, α^{4t+2i}, α^{8t+2i}}, i = 0, 1, …, t − 1

are the base blocks for an S(2, 4, v).

Theorem 2.3. Let 4t + 1 = p^{n}, p prime, and let α be a primitive root of GF (p^{n}). Then there exists a pair of integers c, q such that (α^{c} + 1)/(α^{c} − 1) = α^{q}. Let V = GF (p^{n}) × {1, 2, 3} ∪ {∞}. Then the blocks

{α_{1}^{2i}, α_{1}^{2t+2i}, α_{2}^{2i+c}, α_{2}^{2t+2i+c}}

{α_{2}^{2i}, α_{2}^{2t+2i}, α_{3}^{2i+c}, α_{3}^{2t+2i+c}}

{α_{3}^{2i}, α_{3}^{2t+2i}, α_{1}^{2i+c}, α_{1}^{2t+2i+c}}, i = 0, 1, …, t − 1

{∞, 0_{1}, 0_{2}, 0_{3}} are the base blocks with respect to the additive group of GF (p^{n}) of an S(2, 4, 12t + 4).

One of the most frequently used recursive constructions is the so-called

“v → 3v + 1 rule”. Let (V, B) be an S(2, 4, v), and let X be a set such that |X| = 2v + 1, X ∩ V = ∅. Let (X, C) be a resolvable STS(2v + 1) and let R = {R_{1}, …, R_{v}} be a resolution of (X, C), that is, let (X, C, R) be a Kirkman triple system of order 2v + 1; since v ≡ 1, 4 (mod 12), such a system exists. Form the set of quadruples D_{i} = {{v_{i}, x, y, z} : v_{i} ∈ V, {x, y, z} ∈ R_{i}}, and put D = ⋃_{i} D_{i}. Then (V ∪ X, B ∪ D) is an S(2, 4, 3v + 1).

Another construction that deserves mention is the

“direct product rule”. If there exists an S(2, 4, v) and an S(2, 4, w) then there exists an S(2, 4, v.w).

If (V, B) and (W, C) are two such systems, form an S(2, 4, v.w) on the set V × W; if B = {p, q, r, s} and B′ = {x, y, z, u} are two blocks from B and C respectively, form an S(2, 4, 16) on the set B × B′, making sure that {(p, j), (q, j), (r, j), (s, j)} and {(i, x), (i, y), (i, z), (i, u)} are blocks, for i, j = 1, 2, 3, 4.

Hanani’s proof of the existence of S(2, 4, v)s as given in [92] (cf. also [93]) is inductive. As the induction basis, one constructs directly systems of small orders (i.e., of orders 13, 16, 25, 28, 37). Then one uses a pairwise balanced design of index one, PBD(u, K, 1), where K = {4, 5, 8, 9, 12}; such a PBD exists for all u ≡ 0, 1 (mod 4) (see [51]). If (X, B is such a PBD, one takes the (3v + 1)-set V = X × {1, 2, 3} ∪ {∞}; for each block B ∈ B, construct an S(2, 4, 3|B| + 1) on the set B × {1, 2, 3} ∪ {∞}, making sure that for x ∈ X, {∞, (x, 1), (x, 2), (x, 3)} is always a block. The result is an S(2, 4, 3v + 1).

Unfortunately, there is a marked increase in the level of difficulty as the block size increases from three to four. This is reflected among other things in the fact that to-date there does not exist a simple direct proof of the existence of S(2, 4, v)s. By comparison, one has the wonderful Bose’s and Skolem’s constructions for Steiner triple systems (in their most general form, cf. [54]), and the existence proof via the cyclic STSs. A simple direct proof of the existence of S(2, 4, v)s appears very desirable.

3 Automorphisms of Steiner systems S(2, 4, v)

Let (V, B) and (W, C) be two Steiner systems S(2, 4, v). An isomorphism from (V, B) to (W, C) is a 1-1 mapping α : V → W such that ᾱ(B) = C (where ᾱ is the mapping induced on blocks by α). Isomorphism is an equivalence relation, and the systems (V, B) and (W, C) are isomorphic. An automorphism of (V, B) is an isomorphism of (V, B) to itself.

3.1 Cyclic Steiner systems S(2, 4, v)

A Steiner system S(2, 4, v) is cyclic if it contains an automorphism which consists of a single cycle of length v; this automorphism is called a cyclic automorphism. If (V, B) is a cyclic S(2, 4, v), one may assume V = Z_{v}, and α : i → i + 1 (mod v) to be its cyclic automorphism. The blocks of an S(2, 4, v) are partitioned into orbits under the action of the cyclic group generated by α. Each orbit of blocks is completely determined by any of its blocks, and B is determined by a collection of blocks called base blocks (sometimes also called starter blocks or initial blocks) containing one block from each orbit.

The possible orbit lengths of blocks in a cyclic S(2, 4, v) are v and \frac{v}{4}; an orbit of length v is full, that of length \frac{v}{4} is short. In a cyclic S(2, 4, v) with v ≡ 1 (mod 12) there are \frac{v−1}{12} full orbits of blocks (and no short orbit) while if v ≡ 4 (mod 12), there are \frac{v−4}{12} full orbits and one short orbit.

Any set of base blocks of a cyclic S(2, 4, v) with v ≡ 1 (mod 12) yields a (v, 4, 1)- difference family; the latter is a collection of 4-element sets D_{1}, D_{2}, …, D_{n} such that each nonzero residue modulo v can be written in a unique way as d_{i} − d_{j} with d_{i}, d_{j} ∈ D_{m} for some m. Conversely, any (v, 4, 1)-difference family forms a set of base blocks of a cyclic S(2, 4, v) (with v ≡ 1 (mod 12)).

In a similar manner, for v divisible by 4, a modified (v, 4, 1)-difference family is a collection of 4-element sets D_{1}, D_{2}, …, D_{n} such that each nonzero residue modulo v except for ±\frac{v}{4} and \frac{v}{2} can be written in a unique way as d_{i}−d_{j} with d_{i}, d_{j} ∈ D_{m} for some m. Clearly, adjoining the base block \{0, \frac{v}{4}, \frac{v}{2}, \frac{3v}{4}\} to a modified (v, 4, 1)-difference family results in a set of base blocks of a cyclic S(2, 4, v) with v ≡ 4 (mod 12), and conversely, the set of base blocks of a cyclic S(2, 4, v) with v ≡ 4 (mod 12) minus the base block corresponding to the short orbit yields a modified (v, 4, 1)-difference family.

Bose’s first construction (Theorem 2.2 above) yields cyclic S(2, 4, v)s whenever v = 12t+1 is a prime. The smallest cyclic systems thus obtained are those of orders 13, 37, 61, 73, 97, …

There exists no cyclic S(2, 4, v) for v = 16, 25, 28. This is established by showing the nonexistence of a (v, 4, 1)- or a modified (v, 4, 1)-difference family, as the case may be.

Further progress on the existence of cyclic S(2, 4, v)s is more recent. It is shown in [24],

[45] that a cyclic S(2, 4, v) and a cyclic S(2, 4, 4v) exists whenever v is a product of primes, each congruent to 1 modulo 12. Buratti [23] has shown that a cyclic S(2, 4, 4v) exists for any v such that any prime factor p of v is congruent to 1 modulo 6 and gcd(\frac{p−1}{6}, 20!) ≠ 1. In [29], Buratti provided some explicit constructions of cyclic S(2, 4, v)s and also showed that there exists a cyclic S(2, 4, 4p) if p = 6n + 1 is a prime > 7 and the least prime factor of n is not greater than 19. Chang [38] has shown that there exists a cyclic S(2, 4, 4^{n}u) where n ⩾ 3 is a positive integer and u is a product of primes, each congruent to 1 modulo 6, or n = 2 and u is a product of primes each congruent to 1 modulo 6 such that gcd(u, 7.13.19) ≠ 1.

Several recursive constructions for cyclic S(2, 4, v)s similar to recursive constructions for 1-rotational S(2, 4, v)s (cf. Section 3.2 below) were obtained in [56], [103], [104].

For small orders, it has been established [2], [44] that cyclic Steiner systems S(2, 4, v) exist for all v ≡ 1 or 4 (mod 12), v ⩽ 613, except for v = 16, 25, 28, for which they do not exist.

Even though it has been conjectured that cyclic S(2, 4, v)s exist for all admissible v ⩾ 37, the existence question for cyclic S(2, 4, v)s remains open.

3.2 1-rotational Steiner systems S(2, 4, v)

A Steiner system S(2, k, v) is k-rotational if it has an automorphism consisting of a fixed point and k disjoint cycles of length \frac{v−1}{k}. Thus a 1-rotational S(2, 4, v), (V, B), may be assumed to have V = Z_{v−1} ∪ {∞}, with the 1-rotational automorphism given by i → i + 1(mod v − 1), ∞ → ∞. For the existence of a 1-rotational S(2, 4, v) it is necessary that v ≡ 4 (mod 12). The designs of points and lines in affine spaces AG(d, 4) provide examples of 1-rotational S(2, 4, v)s. It follows from a construction of Moore [139] that a 1-rotational S(2, 4, v), v ≡ 4 (mod 12), exists whenever \frac{v−1}{3} is a prime. Colbourn and Colbourn [50] were apparently the first to provide a recursive construction for 1-rotational S(2, k, v)s. From a given 1-rotational S(2, 4, 3u+1) and a 1-rotational S(2, 4, 3v+1), where gcd(u, 6) = 1, they construct a 1-rotational S(2, 4, 3uv+1). As a corollary they obtain that a 1-rotational S(2, 4, v) exists for all v = 3.5^{n} + 1, n ⩾ 0. Another recursive construction for 1-rotational S(2, 4, v)s using difference matrices was given by Jimbo [101], [103]. Liaw [118], apparently unaware of the results of Colbourn, Colbourn and Jimbo, has shown that if there exists a 1-rotational S(2, 4, 3u + 1) and a 1-rotational S(2, 4, 3v + 1) such that 9 does not divide v − 1 then there exists a 1-rotational S(2, 4, 3uv + 1). As a corollary he obtains that there exists a 1-rotational S(2, 4, v) whenever v = 3p_{1}^{α_{1}} … p_{n}^{α_{n}} + 1 where p_{i} is prime, p_{i} ≡ 1(mod 4), or p_{i} = \frac{4^{m}−1}{3}, and there is at most one p_{i} such that p_{i} = \frac{4^{m}−1}{3} where m ≡ 0(mod 3), and α_{i} = 1 for this p_{i}. It is pointed out in [106] that for all such orders v there exists a Z-cyclically resolvable 1-rotational S(2, 4, v) (i.e. one in which the parallel classes are generated cyclically).

It has been conjectured that a 1-rotational S(2, 4, v) exists for all v ≡ 4 (mod 12), except for v = 28 for which it is known not to exist, but this remains unresolved.

4 Enumeration of Steiner systems S(2, 4, v)

Let N(v) be the number of nonisomorphic S(2, 4, v)s. The smallest nontrivial S(2, 4, v) is the unique S(2, 4, 13) which is the design of points and lines of P G(2, 3), the projective plane of order 3. The design is cyclic, and may be presented as

(V, B) = (Z_{13}, {0, 1, 4, 6} mod 13).

Its full automorphism group is doubly transitive of order 5616.

The Steiner system S(2, 4, 16) is also unique; it is the design of points and lines of AG(2, 4), the affine plane of order 4. The design is not cyclic but is 1-rotational, and is doubly transitive as well. Its full automorphism group is of order 16.15.12.2.

The early papers towards enumeration of S(2, 4, v) for the next two orders 25 and 28 include [150], [151], [166], [17], [19], [157], [110]. In [109] it was shown that there are exactly 16 Steiner systems S(2, 4, 25) with a nontrivial automorphism group. Spence [178] has completed the enumeration of S(2, 4, 25) by showing that there are exactly 18 nonisomorphic systems. These are listed in full in [129]; their automorphism groups have orders 504, 150, 63, 21, 9 (three times), 6, 3 (eight times), and 1 (twice).

The exact number of systems S(2, 4, 28) is not known at present. But Krčadinac [108] has shown recently that there are exactly 4466 nonisomorphic S(2, 4, 28)s with a nontrivial automorphism group. Together with some S(2, 4, 28)s with trivial automorphism group found in [12], this implies that there are at least 4653 nonisomorphic S(2, 4, 28)s.

These results, together with some known bounds for systems of other small orders, are summarized in the table below. The lower bound for N(37) is from [112], the other values are from [129].

v  13  16  25  28  37  40  49
N(v)  1  1  18  ⩾ 4653 ⩾ 51402 ⩾ 1108800 ⩾ 769
v  52  61  64
N(v) ⩾ 206 ⩾ 18132 ⩾ 14.10^{30}

Concerning N(v) when v is large, Doyen was the first to show that N(v) tends to infinity with v. In [62] he obtained an inequality which, when applied to S(2, 4, v)s, yields

N(v) ⩽ 2^{v^{2}log_{2}v}.

Some additional enumeration results on restricted classes of S(2, 4, v)s deserve mention. Colbourn and Mathon [57] have enumerated small cyclic S(2, 4, v)s. As already mentioned, there is a unique S(2, 4, 13) which is cyclic, and there is no cyclic S(2, 4, v) for v = 16, 25 or 28. The number of cyclic S(2, 4, v)s for v = 37, 40, 49, 52, 61, and 64 is 2, 10, 224, 206, 18132, and 12048, respectively.

Let NR(v) be the number of nonisomorphic resolutions of S(2, 4, v)s (cf. Section 10 below). Very recently, Kaski and Östergård [108] established NR(28) = 7, i.e. there are exactly 7 nonisomorphic resolutions of S(2, 4, 28). Each is coming from a different system except that the so-called Rees unital admits two nonisomorphic resolutions which means that there are exactly 6 nonisomorphic resolvable S(2, 4, 28)s. All these resolutions have been known previously (cf., e.g., [129]), but in [108] it is shown that there are no others.

Krčadinac [112] has enumerated all S(2, 4, 37)s with an automorphism of order 11; there are exactly 284 of these. [In the same paper, he obtained the above mentioned lower bound on N(37).] Gropp [89] has established that there are exactly 226 nonisomorphic abelian S(2, 4, 49).

The complexity of the isomorphism problem for S(2, 4, v)s is unknown. It follows from [6] that isomorphism of S(2, 4, v)s can be tested in subexponential time (cf. also [55]).

5 Steiner systems S(2, 4, v) and algebras

The close relationship, indeed an equivalence, between Steiner triple systems and idempotent totally symmetric quasigroups (sometimes called Steiner quasigroups) is well known (cf. [78], [54]). In what follows we describe the relationship of Steiner systems S(2, 4, v) to another class of algebras, namely to Stein quasigroups.

In the literature one finds described two distinct types of quasigroups, both termed Stein quasigroups. The first kind of these, which appears more common, is defined as a quasigroup (V, ∘) satisfying the law

x ∘ (x ∘ y) = y ∘ x. (1)

This is Stein’s law, sometimes called the first Stein’s law (cf. [59]), or law of semisymmetry.

It is easy to see that Stein quasigroups (S-quasigroups for short) are idempotent, anticommutative (i.e, x ∘ y ≠ y ∘ x for x ≠ y), and nonassociative (cf. [200]).

An example of an S-quasigroup of order 4 is ∘ 1 2 3 4 1 1 3 4 2 2 4 2 1 3 3 2 4 3 1 4 3 1 2 4

The second kind of Stein quasigroups (cf., e.g., [78], [200]) are those satisfying the laws x ∘ x = x (x ∘ y) ∘ y = y ∘ x (y ∘ x) ∘ y = x . (The third of these laws is called in [59] the law of left semisymmetry.) We will call

quasigroups satisfying these laws S^{∗}-quasigroups.

It can be shown that each S^{∗}-quasigroup is an S-quasigroup, but the converse need not hold. However, the S-quasigroup of order 4 given above is also an S^{∗}-quasigroup (cf. [200]).

Given an S^{∗}-quasigroup (V, ∘), |V | = v, define

B = {{x, y, x ∘ y, y ∘ x} : x, y ∈ V, x ≠ y}.

Then (V, B) is an S(2, 4, v).

Conversely, given an S(2, 4, v), (V, B), we can obtain from it an S^{∗}-quasigroup as follows. For every block B ∈ B, choose arbitrarily a bijection ϕ_{B} : B → {1, 2, 3, 4}. On V, define a binary operation ∗ by

x ∗ x = x ∘ x ( = x)

x ∗ y = ϕ_{B}^{−1}(ϕ_{B}(x) ∘ ϕ_{B}(y)) for x ≠ y, x, y ∈ B (where ∘ is a binary operation on {1, 2, 3, 4} as defined by the table above). Then (V, ∗) is an S^{∗}-quasigroup.

6 Subsystems, partial systems and embeddings

A (partial) Steiner system S(2, 4, w), (W, C), is a subsystem of a Steiner system S(2, 4, v), (V, B), if W ⊆ V and C ⊆ B. We also say in this case that (W, C) is embedded in (V, B).

Ganter [74] and Quackenbush [152] have shown that every partial system S(2, 4, w) can be embedded in a finite S(2, 4, v). Their result is commonly referred to as “Ganter’s Theorem”. However, their proof only provides an embedding which at worst is exponential in the size of the partial system. A proof of the existence of a polynomial size embedding, as it was proved to exist in the case of partial Steiner triple systems (cf. [54]), remains elusive so far.

Theorem 6.1 ((Ganter’s theorem)). Every partial Steiner system S(2, 4, w) can be embedded in some Steiner system S(2, 4, v).

Brouwer and Lenz [20], [21] were the first to study embeddings of S(2, 4, w)s into S(2, 4, v)s. It is easy to see that the necessary conditions for the existence of such an embedding are w = v (trivial embedding) or v ⩾ 3w + 1 (proper embedding). Wei and Zhu [190], [191] have shown the sufficiency of these conditions for all w > 85, w ≠ 133, and subsequently Rees and Stinson [155] have completed the proof of what is now referred to as the Rees-Stinson Theorem.

Theorem 6.2 ((Rees-Stinson Theorem)). Let w, v be positive integers, w, v ≡ 1 or 4 (mod 12). An S(2, 4, w) can be properly embedded in some S(2, 4, v) if and only if v ⩾ 3w + 1.

The paper [155] contains many involved constructions and is a fine example of skillful use of design-theoretic techniques. The main result of [155] actually contains a more general theorem than Theorem 6.2 above, as it also deals with embeddings of Steiner systems S(2, 4, v) with a hole.

An S(2, 4, v) with a hole of size w (also called an incomplete design IPBD(v, w; {4}), cf. [51]) is a triple (V, W, B) where W ⊂ V, B is a set of 4-tuples of elements of V such that every 2-subset of V is contained in exactly one 4-tuple of B except when both elements of the 2-subset belong to W in which case this 2-subset is contained in no 4-tuple of B. For example, if one deletes the 4-tuples of an S(2, 4, w) which is embedded in an S(2, 4, v), then an S(2, 4, v) with a hole of size w (or an IPBD(v, w, {4})) results. However, the size of the hole is not necessarily an admissible order congruent to 1, or 4 (mod 12). If, on the other hand, the hole has an admissible order then any subsystem of that order can be put in the hole. This is often referred to as the replacement property of Steiner systems S(2, 4, v). The following is the general version of the Rees-Stinson theorem.

Theorem 6.3. A Steiner system S(2, 4, v) with a hole of size w < v exists if and only if v ⩾ 3w + 1, and

(i) v ≡ w ≡ 1 or 4 (mod 12), or

(ii) v ≡ w ≡ 7 or 10 (mod 12).

Very recently, embeddings of resolvable S(2, 4, v)s into resolvable S(2, 4, v)s were considered in [81] (for resolvable S(2, 4, v)s, cf. Section 10 below). It is shown in [81] that a resolvable S(2, 4, w) can be embedded in a resolvable S(2, 4, v) if and only if v ⩾ 4w, v ≡ w ≡ 4 (mod 12) with 179 possible exceptions, but certainly whenever w > 1840 (for details, see [81]).

Another type of an embedding is that of an S(2, 4, v) into an S(3, 4, v), that is, into a Steiner quadruple system of the same order v. (The term “completion” would be more appropriate here.) For this to be possible, it is necessary that v ≡ 4 (mod 12). If an S(2, 4, v) is embedded into an SQS(v), the latter is said to contain a spanning block design. Lindner conjectured (cf. [95] or [100]) that an SQS(v) with a spanning block design exists for all v ≡ 4 (mod 12). Historically, the problem which was considered first, and whose solution would imply the existence of an SQS with a spanning block design, was that of the existence of an SQS(v) partitionable into \frac{v−2}{2} disjoint S(2, 4, v)s, a much stronger requirement (cf.Section 7). Semakov and Zinoviev [174] and Baker [8] have shown that such a partitionable SQS is provided by (the points and the planes of) AG(2m, 2), the even-dimensional affine geometry over GF(2). Fu [68] has given a quadruplication construction for SQSs with a spanning block design, provided a solution for v = 28 and obtained as a corollary that these exist for all v = 7.4^{n}. Finally, in [101] and [100] it was shown that an SQS(v) with a spanning block design exists if and only if v ≡ 4 (mod 12).

Theorem 6.4. There exists an S(2, 4, v) which can be embedded in an SQS(v) if and only if v ≡ 4 (mod 12).

We note that the replacement property does not hold here any more.

When v ≡ 1 (mod 12), a completion of S(2, 4, v) to an SQS of the same order is not possible but one may look for an embedding into an SQS(v + 1). If such an embedding exists, the SQS(v + 1) is said to contain an almost spanning block design. In [100], the authors present some constructions for SQSs with almost spanning block designs but not much work appears to be done on these designs, and their existence for general v ≡ 2 (mod 12) is still open.

We note that since every S(2, 4, v) may be viewed as a partial SQS, it follows from [74] that every S(2, 4, v) can be embedded in an SQS(u) for some finite u. However, nothing seems to be known about bounds on the size of such an embedding.

Yet another type of embedding involving Steiner systems S(2, 4, v) is that of an embedding of Steiner triple systems, STS(w), into S(2, 4, v)s (see [132]). An STS(w), (W, C), is said to be embedded into a Steiner system S(2, 4, v), (V, B), if W ⊂ V and B|W = C. In other words, C = {C : C ⊂ B for some B ∈ B}. A well-known example of embeddings of STSs into S(2, 4, v)s is provided by the class of affine spaces AG(n, 3) which can be embedded into projective spaces PG(n, 3) by adding a hyperplane at infinity (cf. [96]). The existence, for example, of the century design (cf. Section 9 below) is equivalent to the existence of an embedding of an STS(45) [or of an STS(55)] into an S(2, 4, 100).

It is shown in [132], by using Ganter’s Theorem, that every STS(w) can be embedded into an S(2, 4, v) for some v. The embedding spectrum E(W, C) for an STS(w), (W, C), is defined as E(W, C) = {v: there exists S(2, 4, v) containing (W, C) as a subsystem}, and the embedding spectrum E(w) for an admissible order w is defined as E(w) = ⋃ E(W, C) where the union is taken over all STS(w).

In [132], the spectra E(7) and E(9) have been determined completely (E(9) with one possible exception which was subsequently eliminated by Krcadinac [111]).

Theorem 6.5. (i) E(7) = {v : v ≡ 1, 4 (mod 12), v ⩾ 25}.

(ii) E(9) = {13, 28} ∪ {v : v ≡ 1, 4 (mod 12), v ⩾ 40}.

Also in [132], bounds are provided on m(w) and q(w) where m(w) = min E(w), q(w) = min{q : there exists an S(2, 4, v) containing some STS(w) as a subsystem for all admissible v ⩾ q}. Improved bounds on these quantities are provided for small v, 13 ⩽ v ⩽ 27.

Finally, another kind of embedding is provided by the extension of an S(2, 4, v) into an S(3, 5, v + 1). If there exists an extension of an S(2, 4, v), (V, B) into an S(3, 5, v + 1), say, (V ∪ {∞}, C) then (V, B) is a derived design of (V ∪ {∞}, C) through the point ∞, obtained, obviously, by taking all blocks of C containing ∞ and deleting ∞ from the latter. Since an affine space AG(n, q) can be extended to an inversive space S(3, q + 1, q^{n} + 1), it follows that for each positive integer n there exists an S(2, 4, 4^{n}) which can be extended to an S(3, 5, 4^{n} + 1). So, for example, the (unique) S(2, 4, 16) can be extended to the (unique) S(3, 5, 17). On the other hand, since a necessary condition for the existence of an S(3, 5, u) is u ≡ 2, 5, 17, 26, 41, or 50 (mod 60), it follows that a necessary condition for the existence of an S(2, 4, v) extendable to an S(3, 5, v + 1) is that v ≡ 1, 4, 16, 25, 40, or 49 (mod 60). The S(2, 4, 25) No.1 in [129] (in [51]) can be extended to the only known S(3, 5, 26); the latter is cyclic but it is not known whether it is unique up to isomorphism. But the necessary and sufficient conditions for the existence of an S(3, 5, v) are not known. In fact, it is not even known whether an S(3, 5, 41) or an S(3, 5, 50) exists or not.

7 Disjoint systems, intersections and large sets

Two Steiner systems S(2, 4, v) (V, B), (V, B′) are said to intersect in s blocks if |B ∩ mathcalB′| = s; if B ∩ B′ = ∅ then they are said to be disjoint. Extending a well-known result of Teirlinck for STSs, Ganter, Pelikán and Teirlinck [77] (cf. also [55]) proved the following.

Theorem 7.1. Let (V, B_{1}), (V, B_{2}) be any two Steiner systems S(2, 4, v). Then there exist two disjoint systems (V, B_{1}′), (V, B_{2}′) such that (V, B_{1}) is isomorphic to (V, B_{1}′) and (V, B_{2}) is isomorphic to (V, B_{2}′).

The intersection problem for S(2, 4, v) is to determine the set J(v) of all integers s for which there exist two Steiner systems S(2, 4, v) intersecting in s blocks. The intersection problem for S(2, 4, v)s was considered by Colbourn, Hoffman and Lindner in [52]. It has been known previously that J(13) = {0, 1, 2, 3, 4, 5, 7, 13} and J(16) = {0, 1, 2, 3, 4, 5, 6, 8, 12, 20}. They determined the set J(v) completely for all orders v ≡ 1, 4 (mod 12), with some possible exceptions for orders 25, 28 and 37. Let b_{v} = \frac{v(v−1)}{12}, and let I(v) = {0, 1, …, b_{v}} \ {b_{v} − 7, b_{v} − 5, b_{v} − 4, b_{v} − 3, b_{v} − 2, b_{v} − 1}. It is shown in [52] that J(v) = I(v) for all admissible v ⩾ 40.

However, J(25) ≠ I(25) since, as is shown in [52], 42 ∉ J(25), and 44 ∉ J(25). On the other hand, {0, 1, …, 30} ∪ {32, 35, 36, 38, 50} ⊆ J(25), which leaves each s ∈ {31, 33, 34, 37, 39, 40, 41} in doubt as to its belonging to J(25). Moreover, it is shown in [52] that I(28) \ {44, 46, 49, 50, 52, 53, 54, 57} ⊆ J(28), and

I(37) \ {64, 66, 76, 82, 84, 85, 88, 90, 91, 92, 93, 94, 96, 97, 98, 99, 100, 101} ⊆ J(37).

In particular, the above results imply that for every admissible v, there exists a pair of disjoint S(2, 4, v)s. Not much is known, however, about larger cardinality sets of mutually disjoint S(2, 4, v)s. The maximum possible number of mutually disjoint S(2, 4, v)s equals \frac{(v−2)(v−3)}{2}; any set of \frac{(v−2)(v−3)}{2} disjoint S(2, 4, v)s is called a large set of S(2, 4, v)s and is denoted by LS(2, 4, v). However, for only two values is a large set of S(2, 4, v)s known: an LS(2, 4, 13) containing 55 mutually disjoint S(2, 4, 13)s [46], and an LS(2, 4, 16) containing 91 disjoint S(2, 4, 16)s [128].

The difficulty of constructing large sets of S(2, 4, v)s is partly due to the fact that the number of systems in a large set LS(2, 4, v) is quadratic in v. So, for example, an LS(2, 4, 25) must contain 253 disjoint systems; the existence of such a large set is unknown at present.

Quite recently, the so-called triangle intersection problem for S(2, 4, v)s was considered in [39]. Given two Steiner systems S(2, 4, v), say, (V, B_{1}), (V, B_{2}) on the same set, and two blocks B, B′, B ∈ B_{1}, B′ ∈ B_{2}, the number of triangles that these blocks may have in common is 0, 1, or 4. In the triangle intersection problem, one is asked to determine the possible number of triangles that the two systems may have in common. In [39], the set of these numbers is completely determined for all v ⩾ 121 and for v = 40, and for all v, 49 ⩽ v ⩽ 112, it is determined with one possible exception.

8 Independent sets and arcs in Steiner systems S(2, 4, v)

A subset S ⊂ V in a design D = (V, B) is independent if there is no B ∈ B contained in S. An independent set is maximal if for all x ∈ V \ S, the set S ∪ {x} is not independent. The independence number α(D) of D is defined as α(D) = {max|S| : S is an independent set in D}.

If S is an independent set in an S(2, k, v), then |S| ⩽ \frac{k−2}{k−1}(v − 1) + 1. Thus for an S(2, 4, v), |S| ⩽ \frac{2v+1}{3} where equality can be attained for v ≡ 4, 13 (mod 36). Indeed, taking an S(2, 4, v), (V, B), and embedding it into an S(2, 4, 3v + 1), (W, C), by applying the v → 3v + 1 rule (cf. Section 2), it is readily seen that the set W \ V is a (maximum) independent set. This independent set is also an (0, 3)-set (see below).

For example, the unique S(2, 4, 13) contains independent sets of any size up to 9, maximal independent sets of sizes 7 and 9, and its independence number α = 9. The unique S(2, 4, 16) contains independent sets of sizes up to 9, maximal independent sets of size 9, and its independence number α = 9 (it also contains a maximum arc of size 6, see below).

On the other hand, a lower bound for the independence number of D is obtained in [86] where it is shown that for sufficiently large v, α(D) ⩾ cv^{\frac{2}{3}} (log v)^{\frac{1}{3}} for some constant c. It was shown later in [165] that for sufficiently large v there exists an S(2, 4, v) D^{∗} whose independence number α(D^{∗}) satisfies

cv^{\frac{2}{3}} (log v^{\frac{1}{3}} ) ⩽ α(D^{∗}) ⩽ dv^{\frac{2}{3}} (log v^{\frac{1}{3}} )

for some constants c, d.

A special type of an independent set is an arc. An s-arc in a Steiner system S(2, k, v) is a set of s points no three of which are contained in a block. An arc is complete if any point of the S(2, k, v) is contained in at least one secant block (a block which contains exactly two elements of the arc). In other words, a complete arc cannot be contained in a larger arc. Examples of complete arcs can be found in [159], [161], [162]. It is shown in [159] that the minimum possible size s of a complete arc in an S(2, k, v) satisfies s^{2}(k − 2) − s(k − 4) − 2v = 0. It follows that the minimum possible size of a complete arc in an S(2, 4, v) equals \sqrt{v}.

In the same paper [159], the question is posed whether it is possible to partition the set of elements of an S(2, 4, v), v a square, into \sqrt{v} complete \sqrt{v}-arcs. Examples of such a partition are given for the unique S(2, 4, 16) and for one of the S(2, 4, 25)s (No.6 in [110]). Some further such partitions are presented in [149] where an infinite class of S(2, 4, v)s admitting such a partition is given.

If for each element x of a complete arc S there exists a unique block B containing x but no other element of S, then the complete arc is called an oval (and such a block is called a tangent block). There seems to have been very little work done on ovals in Steiner systems S(2, 4, v), although some observations are made in [196].

An arc with maximum size \frac{v+2}{3} = r+1 is a maximum arc or a hyperoval. The necessary condition for the existence of a hyperoval in an S(2, 4, v) is v ≡ 4 (mod 12) [61]. While examples of hyperovals in S(2, 4, v)s were constructed in [60], [134], the above necessary condition was shown to be sufficient in [88] and independently in [125]. An S(2, 4, v) with a maximum arc admits a 2-colouring of type AC (cf. Section 9). Some further recursive constructions for S(2, 4, v)s with maximum arcs are given in [133].

Another type of independent sets are the s-sets of type (m, n) introduced and studied in [156]. In general, an s-set of type (m, n), 0 ⩽ m < n ⩽ k − 1, in a Steiner system S(2, k, v), (V, B), is a subset S ⊂ V, |S| = s such that |S ∩ B| = m or n for all B ∈ B. In the case of S(2, 4, v)s, one is interested in the s-sets of type (0, 2), (0, 3), and (1, 3). Sets of type (0, 2) are hyperovals. The necessary and sufficient condition for the existence of a (0, 3)-set in an S(2, 4, v) is v ≡ 4, 13 (mod 36) [156], [196]. The most interesting of the above cases is that of (1, 3)-sets. It is shown in [156] that a necessary condition for an S(2, 4, v) to contain a (1, 3)-set is v ≡ 4 (mod 24), and v must be a square; the size s of such an (1, 3)-set is s = (v − \sqrt{v})/2 or s = (v + \sqrt{v})/2. The smallest v satisfying this necessary condition is v = 100, and it was shown very recently [65], [66] that such an S(2, 4, 100) containing (1, 3)-sets of sizes 45 and 55, respectively, indeed exists (cf. Section 9 below, colouring of type B).

Finally, a special class of independent sets is provided by blocking sets (independent sets whose complements are also independent, cf. Section 9 below). Not every system S(2, 4, v) contains a blocking set since every such S(2, 4, v) must be 2-colourable.

9 Colourings of Steiner systems S(2, 4, v)

The colourings of Steiner systems S(2, 4, v) are basically of two kinds: element-colourings and block-colourings (although one may consider colouring both, elements and blocks, simultaneously). In this section we consider the first of these two kinds.

Let S = (V, B) be a Steiner system S(2, 4, v). A (proper element-) colouring of S is a mapping ϕ : V → C such that for all B ∈ B, |ϕ(B)| > 1 where ϕ(B) = ∪_{x∈B}ϕ(x). Here C is the set of colours. For each c ∈ C, the set ϕ^{−1}(c) = {x : ϕ(x) = c} is a colour class. If |C| = m, we speak of an m-colouring of S. The chromatic number of S, χ(S), is the smallest m for which there exists an m-colouring of S. If χ(S) = m, the system S is said to be m-chromatic.

In other words, in a colouring of S, no block is monochromatic. This type of colouring has sometimes been called weak (and is even occasionally referred to as classical colouring), in accordance with Berge’s definition of weak and strong colouring of hypergraphs, respectively. However, strong colourings of hypergraphs require all elements of a block (=hyperedge) to be coloured with a different colour, and thus are of no interest with regard to colouring Steiner systems (or other block designs) as this requirement would imply that each element of V must get a different colour (but see the classical strong colourings mentioned below among colourings with specified block-colour patterns).

Unlike Steiner triple systems whose chromatic number must be at least 3 if v > 3, Steiner systems S(2, 4, v) may be 2-chromatic. In fact, it is easily seen that for v ∈ {4, 13, 16}, the unique S(2, 4, v) is 2-chromatic. Two of the 18 nonisomorphic S(2, 4, 25) are also 2-chromatic. It was shown in [97] that for all v ≡ 1 or 4 (mod 12), except possibly for v = 37, 40, 73, there exists a 2-chromatic S(2, 4, v). More recently, the existence of a 2-chromatic S(2, 4, v) with v ∈ {37, 40, 73} was established in [67], thus we have:

Theorem 9.1. A 2-chromatic S(2, 4, v) exists for all admissible orders v ≡ 1 or 4 (mod 12).

Let us observe that the above result was established in terms of the existence of a blocking set in S(2, 4, v). A blocking set in (V, B) is a subset X of V which is independent and whose complement V \X in V is also independent. Thus a blocking set in an S(2, 4, v) and its complement are the two colour classes in a 2-colouring of V.

The smallest 3-chromatic S(2, 4, v) has order v = 25. The following was proved in [164].

Theorem 9.2. A 3-chromatic S(2, 4, v) exists if and only if v ≡ 1 or 4 (mod 12) and v ⩾ 25.

Combining an early result of Erdős with Ganter’s theorem on completion of partial S(2, 4, v)s (see Section 6 above), one obtains immediately that there exist Steiner systems S(2, 4, v) with arbitrarily high chromatic number. However, in a result paralleling a similar result for STSs, Linek and Wantland [124] established the following much stronger statement.

Theorem 9.3. For each m ⩾ 2, there exists a constant v_{m} such that for all admissible orders v ⩾ v_{m}, there exists an m-chromatic S(2, 4, v).

Theorems 9.1 and 9.2 show that v_{2} = 4, v_{3} = 25 but the value of v_{m} remains unknown for m ⩾ 4.

The complexity of computing the chromatic index of S(2, 4, v)s appears to be unknown. Voloshin’s concept of mixed hypergraph colourings (cf. [189]) where each block is

considered as a C-edge and a D-edge simultaneously requires the absence of not only monochromatic but also of polychromatic blocks, that is no block in a colouring can have all its elements coloured the same or all its elements coloured with pairwise distinct colours. A refinement of this concept leads to a consideration of several types of colourings with specified block-colour patterns. If the block size is k, there are P_{k} possible colour patterns on a block where P_{k} is the number of partitions of k. For Steiner systems S(2, 4, v), the block size is 4, and there are altogether 5 partitions of the number 4: (4), (3, 1), (2, 2), (2, 1, 1), (1, 1, 1, 1) which we denote, in this order, as of type A, B, C, D, or E. If we take S ⊆ {A, B, C, D, E}, S ≠ ∅, we can define a colouring of type S as a colouring where each block B ∈ B is coloured with a pattern from S only. Since there are 31 distinct nonempty subsets of {A, B, C, D, E}, there are 31 distinct types of colouring one might consider. For example, our “classical” colouring is of type BCDE, the strong colouring mentioned at the beginning of this section is of type E, and the Voloshin-type colouring (cf. [189]) is of type BCD.

A new phenomenon which arises here is that of uncolourability. Unlike in the classical case, it may happen that for certain given types S of colourings, a given Steiner system S(2, 4, v) cannot be coloured with block-colour patterns from S; in this case, it is Suncolourable. Clearly, if an S(2, 4, v) is S-uncolourable then S ⊆ {B, C, D}. In [165],

[86] it is shown that for sufficiently large orders v there exist S(2, 4, v) with maximal independent sets of size o(v). This implies that any such S(2, 4, v) is BCD-uncolourable (i.e., there is no colouring satisfying Voloshin’s condition).

The question one asks in connection with colourings of type S is not only about the existence or nonexistence of colourings but also about how many colours are possible in a colouring if one exists. Here one must insist that in an m-colouring, all m colours are used (a requirement unimportant in classical type colourings) since the existence of an m-colouring no longer implies the existence of an (m + 1)-colouring.

Given an S(2, 4, v), (V, B), define the colouring spectrum

Ω_{S}(V, B) = {m : (V, B) has an m-colouring of type S}, and

Ω_{S}(v) = ∪Ω_{S}(V, B) where the union is taken over all systems of order v.

Clearly, we have Ω_{BCDE}(V, B) = {χ, χ + 1, …, v}, and

Ω_{BCDE}(v) = {2, 3, …, v} where χ is the (classical) chromatic number of (V, B).

Trivially, Ω_{A}(v) = {1}, Ω_{E}(v) = {v}, Ω_{ABCDE}(v) = {1, 2, …, v}.

Furthermore, while the trivial S(2, 4, 4) obviously has a colouring of type C, a simple calculation shows that any S(2, 4, v) with v ⩾ 13 is C-uncolourable [134].

A quite interesting case of colourings is provided by colourings of type B. In such a colouring, each block must have three elements coloured with the same colour, and the fourth element with a different colour. Starting with the trivial S(2, 4, 4) coloured in such a way, and applying the v → 3v + 1 construction (cf. Section 2) consecutively k − 2 times, one obtains an S(2, 4, v) where v = \frac{3^{k}−1}{2} with a k-colouring of type B ([134]). The type B colourable Steiner systems S(2, 4, v) obtained in this way include the projective spaces PG(k, 3); although the class of S(2, 4, v)s in question is quite extensive, their order is necessarily of the form v = \frac{3^{k}−1}{2}.

Are there any other S(2, 4, v)s which admit colouring of type B? The following necessary conditions are taken from [134] (conditions (i), (ii), (iii)) and from [65] (conditions (iv) and (v)).

Lemma 9.4. If (V, B) is an S(2, 4, v) with a k-colouring of type B and x_{i} is the size of the ith colour class then

(i) x_{i} ≡ 1, 3 (mod 6) for 1 ⩽ i ⩽ k, with precisely one x_{i} ≡ 1 (mod 6);

(ii) Σ\binom{x_{i}}{2} = Σx_{i}x_{j} = \frac{v(v−1)}{4};

(iii) x_{i} ⩽ \frac{2v+1}{3} for 1 ⩽ i ⩽ k;

(iv) x_{i} = \frac{2v+1}{3} for some i if and only if the S(2, 4, v) can be obtained from an S(2, 4, v − x_{i}) using the v → 3v + 1 rule;

(v) for 1 ⩽ i < j ⩽ k, (x_{i} − x_{j})^{2} ⩾ x_{i} + x_{j}.

These conditions are quite stringent, since, besides the orders of the projective spaces PG(k, 3), there are only three solutions for v ⩽ 121 that satisfy the conditions of Lemma 9.4:

1. v = 61, (x_{1}, x_{2}, x_{3}) = (3, 19, 39)

2. v = 100, (x_{1}, x_{2}) = (45, 55)

3. v = 109, (x_{1}, x_{2}, x_{3}) = (1, 45, 63).

The case (2) is most intriguing as it has been around for quite some time (cf., e.g, [156]). The problem of finding a system with a colouring of type B in this case is equivalent to the problem of finding an S(2, 4, 100) having a (classical) 2-colouring without blocks coloured with the pattern 2 + 2; it has been dubbed the “century design”. Until recently, no solution to either of 1., 2. or 3. was known. In a recent superb paper [65], a solution was found for each of these cases (cf. also [66] for the century design). The v → 3v+1 rule implies the existence of three new infinite series of type B colourable systems S(2, 4, v), namely those of orders v = 3^{n}v_{0} + \frac{3^{n}−1}{2} where v_{0} ∈ \{61, 100, 109\}, and n is a nonnegative integer. For example, there exists an S(2, 4, 184) with a 4-colouring of type B. In fact, the number of such systems is enormous, as there exists an enormous number of Kirkman triple systems of order 123, cf. [129].

Colourings of type D are interesting in that systems admitting such colouring with a small number of colours are rather exceptional. In particular, for k ⩽ 5 there are only finitely many S(2, 4, v)s with a k-colouring of type D. A 3-colouring of type D exists only if v = 4; no 4-colouring of type D exists for any S(2, 4, v); and a 5-colouring of type D exists only if v ∈ {13, 16, 25} [134]. Thus if there is an m-colouring of type D with v > 25 then m ⩾ 6. It is shown in [134] that Ω_{D}(13) = {5, 6}, and Ω_{D}(16) = {5, 6, 7} but determining Ω_{D}(v) for larger v appears more difficult.

One interesting result regarding colourings of type D obtained in [134] is as follows.

Theorem 9.5. Let k be an arbitrary integer ⩾ 2, and assume there exists a k-colouring of S(2, 4, v) of type D in which all colour classes have the same cardinality. Then k = 5, and v = 25.

The colouring spectrum for colourings of type AC (only monochromatic blocks or blocks with colour pattern 2 + 2 are allowed) has also been completely determined. It was shown in [134] that Ω_{AC}(v) = {1} whenever v ≡ 1 (mod 12); on the other hand, if v ≡ 4 (mod 12), then Ω_{AC}(v) ⊆ {1, 2}, and it was conjectured in [134] that equality always holds. This has been proved in [88] where an S(2, 4, v) with a maximal arc was constructed for all v ≡ 4 (mod 12); it is not hard to see that an S(2, 4, v) with a maximal arc admits a 2-colouring of type AC.

Further results on certain colourings of type S when |S| = 2 are contained in [134], [84], in particular, for colourings of type AD, AE, and BC; colourings of the latter type are called bicolourings in [84].

10 Block-colourings and resolvability

A Steiner system S(2, 4, v) (V, B) is resolvable if B can be partitioned into \frac{v−1}{3} parallel classes. Here a parallel class P is a subset of B such that each x ∈ V is contained in exactly one block of P, i.e., P is a partition of V.

The (up to an isomorphism) unique S(2, 4, 16) which consists of points and lines of AG(2, 4) is, of course, resolvable.

Since clearly 4 must divide v, a necessary condition for the existence of a resolvable S(2, 4, v) is v ≡ 4 (mod 12). In [94] it is shown that this condition is also sufficient.

Theorem 10.1. A resolvable S(2, 4, v) exists if and only if v ≡ 4 (mod 12).

In what follows we sketch the proof (cf. [3]).

(1) If q = 4t + 1 is a prime power then there exists a resolvable S(2, 4, 3q + 1).

Indeed, let V = GF (q) × Z_{3} ∪ ∞, and let B be determined by the base blocks {0_{0}, 0_{1}, 0_{2}, ∞}, {x^{i}_{j}, x^{i+2t}_{j}, x^{i+t}_{j+1}, x^{i+3t}_{j+1}}, i = 0, 1, …, t − 1, j ∈ Z_{3} where x is a primitive element of GF (q). Then (V, B) is a resolvable S(2, 4, 3q + 1) [92].

(2) If there exists a resolvable S(2, 4, v) and a resolvable S(2, 4, w) then there exists a resolvable S(2, 4, vw) [92].

(3) For v ∈ {100, 172, 232, 388}, there exists a resolvable S(2, 4, v) (a direct construction is provided for each of these orders in [92]; see also [3]).

(4) If there exists a resolvable S(2, 4, 12t + 4) and a resolvable S(2, 4, 12h + 4) where 0 ⩽ h ⩽ t and there exist at least 4 mutually orthogonal latin squares of order t then there exists a resolvable S(2, 4, 60t + 12h + 4).

(5) Main induction step: assume the existence of a resolvable S(2, 4, 12u + 4) for al u ⩽ 30k, k ⩾ 3. Then write

(i) 12u + 4 = 12(30k + h) + 4 = 60(6k − 1) + 12(h + 5) + 4 if 30k ⩽ u ⩽ 30k + 4; (ii) 12u + 4 = 60(6k + 1) + 12h + 4 if 30k + 5 ⩽ u ⩽ 30k + 24; and (iii) 12u + 4 = 60(60k + 5) + 12k + 4 if 30k + 25 ⩽ u ⩽ 30k + 29;

then apply (4) to obtain the existence of a resolvable S(2, 4, 12u + 4) for all u, 30k ⩽ u ⩽ 30(k + 1).

Given a Steiner system S(2, 4, v), say S = (V, B), a block-colouring of S is a mapping ψ : B → C (where C is the set of colours) such that if ψ(B) = ψ(B′) for B, B′ ∈ B, B ≠ B′, then B ∩ B′ = ∅. If the set of colours has cardinality k then ψ is a k-block colouring. For each c ∈ C, ψ^{−1}(c) is a block colour class. The chromatic index of S, denoted χ′(S), is the smallest k for which S admits a k-block-colouring.

Since any block colour class is a partial parallel class, we must have χ′(S) ⩾ |B|/⌊v/4⌋ for any S(2, 4, v) S. In other words, χ′ ⩾ \frac{v−1}{3}. Theorem 10.1 on the existence of resolvable S(2, 4, v)s can therefore be restated as a result on the chromatic index.

Theorem 10.2. For every v ≡ 4 (mod 12) there exists a Steiner system S(2, 4, v) with minimum chromatic index \frac{v−1}{3}.

When v ≡ 1 (mod 12), very little is known about the existence of S(2, 4, v)s with minimum chromatic index. Clearly, such a system cannot be resolvable, and its chromatic index must be at least \frac{v+2}{3}. The chromatic index of the unique S(2, 4, 13) equals 13 since any two of its blocks intersect. The chromatic index of the unique S(2, 4, 16) equals 5 as it is resolvable. The chromatic index of each of the 18 nonisomorphic S(2, 4, 25)s was determined by M. Meszka [131]. One system has chromatic index 10, thirteen of the systems have chromatic index 11, and four systems have chromatic index 12. Thus for v ⩽ 25 there exists no S(2, 4, v) with chromatic index equal to the minimum possible value \frac{v+2}{3}. Whether such systems exist for v = 37 or for any greater order remains an open problem.

As for upper bounds, it is well known (cf. [49]) that χ′(S) ⩽ \frac{4v−1}{3} for any system S. By contrast, the chromatic index of a cyclic S(2, 4, v) cannot exceed v [56].

The complexity of computing the chromatic index of S(2, 4, v)s is unknown.

Two resolutions R_{1}, R_{2} of an S(2, 4, v) are orthogonal if any parallel class of R_{1} = \{P_{1}, …, P_{\frac{v−1}{3}} \} has at most one block in common with any parallel class of R_{2} = \{Q_{1}, …, Q_{\frac{v−1}{3}} \}. An S(2, 4, v) possessing a pair of orthogonal resolutions is said to be doubly resolvable. To each doubly resolvable S(2, 4, v), (V, B), corresponds a \frac{v−1}{3} × \frac{v−1}{3} square array (called a Kirkman square of block size 4) with the property that every element of V is contained in exactly one cell of each row and each column and each cell of the array is either empty or contains a block of B. Such an array is obtained from (V, B) by indexing the rows and columns of the array with the parallel classes of R_{1} and R_{2}, respectively; in the cell labelled (P_{i}, Q_{j}) one places P_{i} ∩ Q_{j}, for all i, j = 1, …, \frac{v−1}{3}. If P_{i} ∩ Q_{j} = ∅, the cell is empty. There exists a doubly resolvable S(2, 4, 4^{n}) for all n ⩾ 3 (see [71], [130]) but the spectrum for doubly resolvable S(2, 4, v) remains undetermined.

In an analogous way, a set of d (⩾ 3) pairwise orthogonal resolutions of an S(2, 4, v) yields a d-dimensional Kirkman cube of block size 4. Recently, Lamken [114] has shown that for d ⩾ 2 and k ⩾ 3 there exists a constant v_{0} = v_{0}(k) such that for all v ⩾ v_{0}, v ≡ k(mod k(k − 1)) there exists an S(2, k, v) with d pairwise orthogonal resolutions. Thus when k = 4, there exists a Steiner system S(2, 4, v) with d orthogonal resolutions, d ⩾ 2 (and thus a d-dimensional Kirkman cube with block size 4) for all v ≡ 4 (mod 12) and v sufficiently large.

11 Packings and coverings

Let v ⩾ k ⩾ t. A t − (v, k, λ) packing is a pair (V, B) where V is a v-element set and B is a collection of k-subsets of V such that each t-subset of V is contained in at most λ blocks of B. The packing number D_{λ}(v, k, t) is the largest possible number of blocks in a t − (v, k, λ) packing. A t − (v, k, λ) packing is optimal (or maximum) if |B| = D_{λ}(v, k, t). Thus an S(2, 4, v) is an optimal packing with D_{λ}(v, k, t) = \frac{v(v−1)}{12}.

By iterating the inequality

D_{λ}(v, k, t) ⩽ ⌊\frac{v}{k} D_{λ}(v − 1, k − 1, t − 1)⌋,

known as the first Johnson bound, Schönheim [173] obtained an upper bound on D_{λ}(v, k, t):

D_{λ}(v, k, t) ⩽ ⌊\frac{v}{k} ⌊\frac{v − 1}{k − 1} … ⌊\frac{v − t + 1}{k − t + 1}λ⌋ … ⌋⌋ = U(v, k, t).

Thus for the case λ = 1, k = 4, t = 2 we obtain

D(v, 4, 2) ⩽ U(v, 4, 2) = ⌊\frac{v}{4}⌊\frac{v − 1}{3}⌋⌋.

The existence problem for maximum 2 − (v, 4, 1) packings was settled by Brouwer [18] who showed that

U(v, 4, 2) − D(v, 4, 2) = \begin{cases}1 & if v ≡ 7, 10 (mod 12), v ≠ 10, 19 or v = 9, 17 \\ 2 & if v = 8, 10, 11 \\ 3 & if v = 19 \\ 0 & otherwise \end{cases}

(The results for v = 17, 19 are due to Stinson [182]).

An interesting question that arises from packings concerns the leave graphs. Given a 2 − (v, 4, 1) packing (X, B), the leave graph of (X, B) is the graph (X, E) where the edges in E are the 2-subsets of X that are not covered by blocks of B. In the table below, the leave graphs of optimal 2 − (v, 4, 1) packings are given for v ∉ {8, 9, 10, 11, 17, 19}.

v ≡  D(v, 4, 2) Leave graph
1, 4 (mod 12)  \frac{v^{2}−v}{12}  empty
0, 3 (mod 12)  \frac{v^{2}−3v}{12}  \frac{v}{3}K_{3}
2, 8 (mod 12)  \frac{v^{2}−2v}{12}  \frac{v}{2}K_{2}
5, 11 (mod 12) \frac{v^{2}−2v−3}{12} K_{1,4} ∪ \frac{v−5}{2}K_{2}
7, 10 (mod 12) \frac{v^{2}−v−18}{12} K_{3,3}
6, 9 (mod 12)  \frac{v^{2}−3v−6}{12} (K_{6} \ K_{4}) ∪ \frac{v−6}{3}K_{3}

A t − (v, k, λ) packing (X, B) is resolvable if B can be partitioned into sets of \frac{v}{k} disjoint blocks each, called parallel classes. For v ≡ 4 (mod 12), a resolvable 2 − (v, 4, 1) packing is the same as a resolvable S(2, 4, v) which exists for all such v (cf. Section 10). When v ≡ 0 (mod 12), resolvable packings exist for all such v ⩾ 24 [93]. When v ≡ 8 (mod 12), there exist resolvable packings for all such v ⩾ 32, except possibly for v ∈ {68, 92, 104, 140, 164, 188, 200, 236, 260, 284, 356, 368, 404, 428, 476, 500, 668, 692}. (The results for v ≡ 0, 8 (mod 12) can be found in [82].)

A cyclic 2 − (v, 4, 1) packing is defined analogously to a cyclic S(2, 4, v). A block orbit is full if there are v distinct blocks in it, and short otherwise. A cyclic 2 − (v, 4, 1) packing having only full block orbits is denoted by 2 − CP (4, 1; v). In [138] and [30], the asymptotic existence of 2 − CP (4, 1; v)s was investigated using the concept of a strong difference family and the theorem of Weil on multiplicative character sums which is well known in number theory.

The known results for 2 − CP (4, 1; v)s can be found in [193], [69], [70], [194], [57], [2], [40]. Note that a cyclic 2 − (v, 4, 1) packing is not necessarily optimal.

A 2 − (v, 4, 1) packing is maximal if it ceases to be a packing whenever a further block is adjoined to it. In [144], Novák considers the size of maximal 2 − (v, 4, 1) packings with a minimum possible number of blocks. Let P_{min}(v, 4, 2) denote such a packing, and let |P_{min}(v, 4, 2)| = m(v). Novák proves the following results for m(v): m(4) = m(5) = m(6) = 1, m(7) = m(8) = m(9) = 2, m(10) = m(11) = m(12) = 3, m(13) = m(14) = 6, m(36t+3) = 36t^{2} +t, m(36t+6) = 36t^{2} +9t+1, m(36t+9) = 36t^{2} +15t+2, m(36t+12) = 36t^{2} + 21t + 3.

Based on these results, Novák conjectures that m(v) ⩽ m(v + 1) for all v ⩾ 4. While the value of m(v) remains undetermined for other values of v, upper bounds are given in [144] for m(v).

Let v ⩾ k ⩾ t. A t − (v, k, λ) covering is a pair (V, B) where V is a set of v elements and B is a collection of k-subsets of V such that each t-subset of V is contained in at least λ blocks of B. The covering number C_{λ}(v, k, t) is the smallest possible number of blocks in a t−(v, k, λ) covering. A t−(v, k, λ) covering is optimal (or minimum) if |B| = C_{λ}(v, k, t). Thus an S(2, 4, v) is an optimal covering with C_{λ}(v, 4, 1) = \frac{v(v−1)}{12}.

By iterating the inequality

C_{λ}(v, k, t) ⩽ ⌊\frac{v}{k} C_{λ}(v − 1, k − 1, t − 1)⌋,

Schönheim [172] obtained a lower bound on C_{λ}(v, k, t):

C_{λ}(v, k, t) ⩾ ⌈\frac{v}{k} ⌈\frac{v − 1}{k − 1} … ⌈\frac{v − t + 1}{k − t + 1}λ⌉ … ⌉⌉ = L(v, 4, 2).

In particular, for the case λ = 1, k = 4, t = 2 one obtains

C(v, 4, 2) ⩾ L(v, 4, 2) = ⌈\frac{v}{4}⌈\frac{v − 1}{3}⌉⌉.

The covering number C(v, 4, 2) was determined for general v by Mills in [135], [136] (some earlier results can be found in [99]):

C(v, 4, 2) − L(v, 4, 2) = \begin{cases}1 & if v = 7, 9, 10 \\ 2 & if v = 19 \\ 0 & otherwise \end{cases}

An interesting question that arises from coverings concerns the shape of excess graphs. Given a 2 − (v, 4, 1) covering (X, B), the excess graph (actually, a multigraph) of (X, B) is the graph (X, E) where E consists of 2-subsets of X with mutliplicity |{B ∈ B : {x, y} ⊆ B}| − 1. The table below lists the excess graphs for the optimal 2 − (v, 4, 1)-coverings, v ∉ {7, 9, 10, 19}.

v ≡  C(v, 4, 2) Excess Graph
1, 4 (mod 12)  \frac{v^{2}−v}{12}  empty
0, 6 (mod 12)  \frac{v^{2}}{12}  \frac{v}{2}K_{2}
3, 9 (mod 12)  \frac{v^{2}+3}{12}  K_{1,4} ∪ \frac{v−5}{2}K_{2}
7, 10 (mod 12) \frac{v^{2}−v+6}{12} triple edge
8, 11 (mod 12)  \frac{v^{2}+v}{12}  G^{∗}
2, 5 (mod 12)  \frac{v^{2}+v+6}{12} G^{∗∗}

where G^{∗} is a 2-regular multigraph with v vertices, and G^{∗∗} is a multigraph with v vertices in which two vertices have degree 5 and the remaining v − 2 vertices have degree 2, or a multigraph in which one vertex has degree 8 and the remaining v − 1 vertices have degree 2.

A t−(v, k, λ) covering (X, B) is resolvable if B can be partitioned into sets of \frac{v}{k} disjoint blocks each (parallel classes). For v ≡ 4 (mod 12), an optimal resolvable 2 − (v, 4, 1) covering is the same as a resolvable S(2, 4, v) (which exists for all such v, [94], cf. Section 10). It was shown in [1], [115] that there exists an optimal resolvable 2 − (v, 4, 1) covering for all v ≡ 0 (mod 4), except possibly when v ∈ {108, 116, 132, 156, 204, 212}.

12 Systems with higher λ and directed systems

There are several ways to extend and generalize the concept of Steiner systems S(2, 4, v). We discuss very briefly two of these; there exists a vast literature which we do not attempt to survey here.

Related to Steiner systems S(2, 4, v) are balanced incomplete designs with the same block size 4 but with higher index λ, BIBD(v, 4, λ). For the existence of a BIBD(v, 4, λ), v ⩾ 4, it is necessary that

λ(v − 1) ≡ 0 (mod 3), λv(v − 1) ≡ 0 (mod 2).

Hanani [92] (see also [93]) was the first to determine that these necessary conditions are also sufficient. The necessary conditions for λ and gcd(λ, 6) are the same, thus it suffices to consider λ ∈ {1, 2, 3, 6}. If λ = 1, we have the case of Steiner systems S(2, 4, v); a BIBD(v, 4, 2) exists if and only if v ≡ 1 (mod 3); a BIBD(v, 4, 3) exists if and only if v ≡ 0, 1 (mod 4); and a BIBD(v, 4, 6) exists for all v ⩾ 4.

Another possible extension of the notion of Steiner systems is to directed systems. A directed balanced incomplete design, DBIBD, with parameters (v, b, r, k, λ) is a BIBD(v, b, r, k, 2λ) where the blocks are ordered k-tuples and where each ordered pair occurs in exactly λ blocks. For example, the block (0, 1, 4, 6) contains the ordered pairs (0, 1), (1, 4), (0, 6), (1, 4), (1, 6), and (4, 6); when developed modulo 7, this base block gives a DBIBD(7, 4, 1). It is easy to see that the existence of a BIBD(v, b, r, k, λ) implies the existence of a DBIBD(v, b, r, k, λ): just write the blocks of the BIBD again in reverse order.

In [183], the following is proved for k = 4.

Theorem 12.1. Let λ, and v ⩾ 4 be positive integers. Then a DBIBD(v, b, r, 4, λ) exists if and only if

λ(v − 1) ≡ 0 (mod 3), λv(v − 1) ≡ 0 (mod 6).

For proof, the authors of [183] used directed group divisible designs which are group divisible designs with directed blocks in which each ordered pair of elements from different groups is contained in the same number of blocks.

13 Miscellanea

13.1 Halving S(2, 4, v)s

An S(2, 4, v) (V, B) is said to have the halving property (or simply can be halved) if there is a partition of the set of blocks B = B_{1} ∪ B_{2} such that B_{1} and B_{2} are isomorphic as hypergraphs. Any permutation α such that αB_{1} = B_{2} is called a halving permutation. An obvious necessary condition for the existence of an S(2, 4, v) with the halving property is v ≡ 1 or 16 (mod 24), as the number of blocks must be even. In [61] it was shown that for v = 16, 25, 40, 64 and for infinitely many other orders there exist S(2, 4, v) which can be halved. This follows form the fact that if all block orbits under an automorphism α of the S(2, 4, v) are of even length then the system can be halved. Thus, in particular, any cyclic S(2, 4, v) with v ≡ 16 (mod 24) and any 2-rotational S(2, 4, v) with v ≡ 1 (mod 24) can be halved. Phelps [148] has established the existence of an S(2, 4, v) that can be halved for all orders v ≡ 1 or 16 (mod 24), except possibly for six orders: 136, 184, 222, 328, 424, 616. The existence of a cyclic S(2, 4, v) has since been proved for the first five of these orders (cf. Section 3.1), and so we have:

Theorem 13.1. There exists an S(2, 4, v) with the halving property if and only if v ≡ 1 or 16 (mod 24) except possibly when v = 616.

13.2 Block-intersection graphs of S(2, 4, v)s

Given an S(2, 4, v), (V, B), its block intersection graph (BIG) has as its vertices the blocks of B; two vertices are adjacent precisely when the corresponding blocks intersect. The BIGs of S(2, 4, v)s are strongly regular with parameters (v, \frac{4(v−4)}{3}, \frac{v+20}{3}, 16). The BIGs of the unique S(2, 4, v)s of orders 13 and 16 are imprimitive (being the complete graph K_{13}, and the complete 5-partite graph K_{4,4,4,4,4}, respectively). The BIGs of S(2, 4, v) with v ⩾ 25 are primitive, and smallest among these have parameters (50, 28, 15, 16). Every BIG of an S(2, 4, v) is Hamiltonian [98].

13.3 Decompositions of S(2, 4, v)s into configurations

A configuration in an S(2, 4, v) is a “small” partial system. When dealing with configurations in S(2, 4, v)s, one usually speaks of points and lines rather then of elements and blocks. There are two distinct (4-point) two-line configurations: two disjoint (parallel) lines (B_{1}), and two intersecting lines (B_{2}). There are five three-line configurations: the star, the hut, the 3-path, the triangle and the 3-PPC (three mutually parallel lines)); cf.

[98] where these configuration are displayed when the lines have three points each. Since the block-intersection graph of any S(2, 4, v) is Hamiltonian (cf. Section 13.2), it follows, similarly as in [98] for Steiner triple systems that every S(2, 4, v) with an even number of blocks can be decomposed into copies of B_{1} or into copies of B_{2}.

A necessary condition for the existence of a decomposition of an S(2, 4, v) into copies of any 3-line configuration is v ≡ 1 (mod 36). It is shown in [14] that there exists an S(2, 4, v) whose lines can be decomposed into triangles if and only if v ≡ 1 (mod 36).

A necessary condition for the existence of a decomposition of an S(2, 4, v) into copies of any 4-line configuration is v ≡ 1 or 16 (mod 48). It is shown in the same paper [14] that if L is a 4-gon or a complete quadrilateral then this necessary condition is also sufficient for the existence of an S(2, 4, v) decomposable into copies of L. Here the 4-gon (l_{1}, l_{2}, l_{3}, l_{4}) is the four-line configuration in which l_{i} and l_{i+1} are intersecting lines but l_{i} and l_{i+2} are parallel (subscripts reduced modulo 4); in the complete quadrilateral, the four lines pairwise intersect but no three intersect in the same point; the complete quadrilateral may be viewed as obtained from the Pasch configuration (with three points per line) by “inserting” an extra point on each line.

Any configuration with no more than three lines cannot be avoided in an S(2, 4, v). It appears that unlike for Steiner triple systems, the questions of avoidance of individual configurations with four or more lines in S(2, 4, v) has not been systematically addressed so far. The importance of this topic is highlighted in [43] where an analysis is performed of the configurations that need to be avoided when constructing good erasure-resilient codes.

13.4 Metamorphosis

The concept of metamorphosis of one kind of design into another kind of design is relatively recent and is due to Lindner [123].

Start with a Steiner system S(2, 4, v), (V, B). For each block B ∈ B, viewed as a complete graph K_{4}, and a vertex x ∈ B, the block B decomposes into a triangle and a 3-star centered at x. Choosing a vertex in each block of B results in a collection of triples, say T, and a collection of 3-stars, say S. If the edges of S can be re-assembled into a collection of triangles (triples) S^{∗} then the Steiner triple system (V, T ∪ S^{∗}) is said to be a metamorphosis of (V, B). For example, one may take the cyclic S(2, 4, 13) with blocks {i, i + 1, i + 4, i + 6}, i = 0, 1, …, 12 (mod 13), delete from each block the last element, and re-assemble the edges of the resulting 3-stars into triples {i, i + 2, i + 7}, i = 0, 1, …, 12(mod 13). Clearly, for a metamorphosis of an S(2, 4, v) into an S(2, 3, v) to exist, it is necessary that v ≡ 1 (mod 12), as v must be an admissible order for both types of designs. Using skew Room squares with holes of size 2, it is shown in [123] that there exists a Steiner system S(2, 4, v) having a metamorphosis into an S(2, 3, v) if and only if v ≡ 1 (mod 12). Similar results are shown also for higher indices λ.

There exist many further results on the metamorphosis of Steiner systems S(2, 4, v) into other types of designs, such as K_{4}-e designs, 4-cycle systems, kite systems etc.; for a survey of these, see [13].

14 Open problems

2.1 Find a direct proof of the existence of S(2, 4, v)s.

3.1 Show that a cyclic S(2, 4, v) exists for all admissible v ⩾ 37. 3.2 Show that a 1-rotational S(2, 4, v) exists for all v ≡ 4 (mod 12), v ≠ 28. 4.1 Determine the number of automorphism-free S(2, 4, 28)s. 4.2 Show that an automorphism-free S(2, 4, v) exists for all admissible v ⩾ 25. 4.3 What is the complexity of the isomorphism problem for S(2, 4, v)s? 6.1 Find a polynomial size embedding for partial systems S(2, 4, v). 7.1 Determine the sets J(25), J(28) and J(37) (cf. Section 7). 7.2 Find good lower bounds for the maximum number of mutually disjoint S(2, 4, v)s. 7.3 Do there exist large sets of disjoint S(2, 4, v)s for v ⩾ 25? 9.1 Determine the complexity of computing the chromatic number of S(2, 4, v)s. 9.2 Find new infinite classes of type B colourable S(2, 4, v)s. 10.1 Find bounds on the chromatic index of S(2, 4, v)s. 10.2 Do there exist, for v ≡ 1 (mod 12), v ⩾ 37, Steiner systems S(2, 4, v) with the

(minimum) chromatic index equal to \frac{v+2}{3}?

10.3 Determine the complexity of computing the chromatic index of S(2, 4, v)s. 10.4 Determine the spectrum for doubly resolvable S(2, 4, v)s. 11.1 Complete the determination of m(v), the size of maximal 2 − (v, 4, 1) packing

with minimum number of blocks.

Acknowledgements

The authors gratefully acknowledge the support by NSERC PGSD scholarship (CR) and by NSERC Grant No. OGP007268 (AR).

References

[1] R.J.R. Abel, A. Assaf, F.E. Bennett, I. Bluskov, M. Greig, Pair covering designs with block size 5, Discrete Math. 307 (2007), 1776–1791.

[2] R.J.R. Abel, M. Buratti, Some progress on (v, 4, 1) difference families and optical orthogonal codes, J. Combin. Theory (A) 106 (2004), 59–75.

[3] I. Anderson, Combinatorial Designs. Construction Methods, Ellis Horwood, 1990.

[4] I. Anderson, Some 2-rotational and cyclic designs, J. Combin. Designs 4 (1996), 247–254.

[5] I. Anderson, N.J. Finizio, Cyclically resolvable designs and triple whist tournaments, J. Combin. Designs 1 (1993), 347–358.

[6] L. Babai, E.M. Luks, Canonical labeling of graphs, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, (1983), 171–183.

[7] C.A. Baker, M. Fleming, N. Shalaby, Large sets of affine planes of order 4: A preliminary report, Congr. Numer. 121 (1996), 77–85.

[8] R.D. Baker, Partitioning the planes of AG_{2m}(2) into 2-designs, Discrete Math. 15 (1976), 205–211.

[9] R.A. Beezer, Counting configurations in designs, J. Combin. Theory (A) 96 (2001), 341–357.

[10] J.-C. Bermond, J. Novák, On maximal systems of quadruples, Graphs, Hypergraphs and Block Systems, Zielona Góra, 1976, pp. 13–19.

[11] T. Beth, D. Jungnickel, H. Lenz, Design Theory, Volume I, Volume II, 2nd Edition, Cambridge Univ. Press, 1999.

[12] A. Betten, D. Betten, V.D. Tonchev, Unitals and codes, Discrete Math. 267 (2003), 23–33.

[13] E.J. Billington, K.A. Dancer, The metamorphosis of designs with block size four: a survey and the final case, Congr. Numer. 164 (2003), 129–151.

[14] E.J. Billington, C.A. Rodger, Partitioning linear spaces into complete quadrilaterals and n-gons, J. Geometry 51 (1994), 13–21.

[15] R.C. Bose, On the construction of balanced incomplete block designs, Ann. Eugenics 9 (1939), 353–399.

[16] P.L.H. Brooke, On the Steiner system S(2, 4, 28) and codes associated with the simple group of order 6048, J. Algebra 97 (1985), 376–406.

[17] A.E. Brouwer, Some non-isomorphic BIBDs B(4, 1; v), Math. Centrum Amsterdam, ZW 102/77 (1977), 1-7.

[18] A.E. Brouwer, Optimal packings of K_{4}’s into a K_{n}, J. Combin. Theory (A) 26 (1979), 278–297.

[19] A.E. Brouwer, Some unitals on 28 points and their embedding in projective planes of order 9, Geometries and Groups, Lecture Notes Math. 893, Springer, 1981, pp. 183–188.

[20] A.E. Brouwer, H. Lenz, Unterräume von Blockplänen, Geometrie-Sympos., Siegen 1977 Birkhäuser Verlag, Basel, 1979, pp. 383–389.

[21] A.E. Brouwer, H. Lenz, Subspaces of linear spaces of line size 4, Europ. J. Combin. 2 (1982), 323–330.

[22] F. Buekenhout, A. Delandtsheer, J. Doyen, P.B. Kleidman, M.E. Liebeck, J. Saxl, Linear spaces with flag-transitive automorphism groups, Geom. Dedicata 36 (1990), 89–94.

[23] M. Buratti, Constructions of (q, k, 1) difference families with q a prime power and k = 4, 5, Discrete Math. 138 (1995), 169–175.

[24] M. Buratti, Improving two theorems of Bose on difference families with q a prime power and k = 4, 5, J. Combin. Des. 3 (1995), 15–24.

[25] M. Buratti, On simple radical difference families, J. Combin. Designs 3 (1995), 161–168.

[26] M. Buratti, From a (G, k, 1) to a (C_{k} + G, k, 1) difference family, Des. Codes Cryptogr. 11 (1997), 5–9.

[27] M. Buratti, 1-rotational Kirkman triple systems generate dicyclic Steiner 2-designs with block size 4, Bull. Inst. Combin. Appl. 26 (1999), 91–95.

[28] M. Buratti, Some regular Steiner 2-designs with block-size 4, Ars Combin. 55 (2000), 133–137.

[29] M. Buratti, Cyclic designs with block size 4 and related optimal optical orthogonal codes, Des. Codes Cryptogr. 26 (2002), 111–125.

[30] M. Buratti, A. Pasotti, Combinatorial designs and the theorem of Weil on multiplicative character sums Finite Fields Appl. 15 2009 332–344

[31] M. Buratti, F. Zuanni G-invariantly resolvable Steiner 2-designs which are 1rotational over G, Bull. Belg. Math. Soc. - Simon Stevin 5 (1998), 221–235.

[32] M. Buratti, F. Zuanni, Some observations on three classical BIBD constructions, Discrete Math. 238 (2001), 19–26.

[33] M. Buratti, F. Zuanni, The 1-rotational (52, 4, 1)-RBIBD’s, J. Combin. Math. Combin. Comput. 30 (1999), 99–102.

[34] T. Cai, Existence of Kirkman systems KS(2, 4, v) containing Kirkman subsystems, Combinatorial Designs and Applications (Ed. W.D. Wallis, H. Shen, W. Wei, L. Zhu), Marcel Dekker, New York, 1990, pp. 3–14.

[35] A. Camina, J. Siemons, Block transitive automorphism groups of 2 − (v, k, 1) block designs, J. Combin. Theory (A) 51 (1989), 268–276.

[36] A. Celona, R. Romano, Some properties of Steiner systems S(2, 4, v) and S(3, 5, v) having transversals, J. Inf. Optim. Sci. 11 (1990), 353–358.

[37] Y. Chang, On cyclic block designs, Rend. Sem. Mat. Messina, Ser.II 9 (2003), 53–62.

[38] Y. Chang, Some cyclic BIBDs with block size four, J. Combin. Designs 12 (2004), 177–183.

[39] Y. Chang, T. Feng, G. Lo Faro, The triangle intersection problem of S(2, 4, v) designs, (to appear).

[40] Y. Chang, J.X. Yin, Further results on optimal optical orthogonal codes with weight 4, Discrete Math. 279 (2004), 135–151.

[41] Y. Chang, R. Fuji-Hara, Y. Miao, Combinatorial constructions for optimal optical orthogonal codes with weight 4, IEEE Trans. Inform. Theory 49 (2003), 1283–1292.

[42] P.L. Check, C.J. Colbourn, Concerning difference families with block size four, Discrete Math. 133 (1994), 285–289.

[43] Y.-M. Chee, C.J. Colbourn, A.C.H. Ling, Asymptotically optimal erasure resilient codes for large disk arrays, Discrete Appl. Math. 102 (2000), 3–36.

[44] K. Chen, R. Wei, A few more cyclic Steiner 2-designs, Electron. J. Combin. 13 (2006), R10, 1–13.

[45] K. Chen, L. Zhu, Existence of (q, k, 1) difference families with q a prime power and k = 4, 5, J. Combin. Designs 7 (1999), 21–30.

[46] L.G. Chouinard II, Partitions of the 4subsets of a 13-set into disjoint projective planes, Discrete Math. 45 (1983), 297–300.

[47] C.J. Colbourn, M.J. Colbourn, Cyclic Steiner systems having multiplier automorphisms, Utilitas Math. 17 (1980), 127–149.

[48] C.J. Colbourn, M.J. Colbourn, On cyclic block designs, C.R. Math. Rep. Acad. Sci. Canada 2 (1980), 95–98.

[49] C.J. Colbourn, M.J. Colbourn, The chromatic index of cyclic Steiner 2-designs, Internat. J. Math. Math. Sci. 5 (1982), 823–825.

[50] C.J. Colbourn, M.J. Colbourn,, A recursive construction for 1-rotational Steiner 2-designs, Congr. Numer. 35 (1982), 163–167.

[51] C.J. Colbourn, J.H. Dinitz (Editors), Handbook of Combinatorial Designs, Second Edition, Chapman and Hall/CRC, 2007.

[52] C.J. Colbourn, D.G. Hoffman, C.C.Lindner, Intersections of S(2, 4, v) designs, Ars Combin. 33 (1992), 97–111.

[53] C.J. Colbourn, R. Mathon Steiner systems, Handbook of Combinatorial Designs, 2nd edition (Ed. C.J. Colbourn, J.H. Dinitz), Chapman-Hall/CRC, 2007, pp. 102– 110.

[54] C.J. Colbourn and A. Rosa, Triple Systems, Clarendon Press, Oxford, 1999.

[55] M.J. Colbourn, Algorithmic aspects of combinatorial designs, Ann. Discrete Math. 26 (1985), 67–136.

[56] M.J. Colbourn, C.J. Colbourn, Recursive constructions for cyclic block designs, J. Stat. Plann. Infer. 10 (1984), 97–103.

[57] M.J. Colbourn, R.A. Mathon, On cyclic Steiner 2-designs, Ann. Discrete Math. 7 (1980), 215–253.

[58] A. Delandtsheer, J. Doyen, J. Siemons, C. Tamburini, Doubly homogeneous 2-(v, k, 1 designs, J. Combin. Theory (A) 43 (1986), 140–145.

[59] J. Dénes, A.D. Keedwell Latin, Squares and their Applications, Akadémiai Kiadó, Budapest, 1974.

[60] R.H.F. Denniston, Some maximal arcs in finite projective planes, J. Combin. Theory 6 (1969), 317–319.

[61] P.K. Das, A. Rosa, Halving Steiner triple systems Discrete Math. 109 (1992), 59–67.

[62] J. Doyen, Non isomorphic block designs with λ = 1, Atti del Convegno di Geometria Combinatoria e sue Applicazioni (Univ. Perugia, 2007) Ist. Mat., Univ. Perugia, Perugia, 1971, pp. 205–207.

[63] J. Doyen, Designs and automorphism groups, Surveys in Combinatorics (Norwich, 1989), London Math. Soc. Lecture Note Ser. 141, Cambridge Univ. Press, Cambridge, 1989, pp. 75–83.

[64] T. Evans, M. Francel, Some connections between Steiner systems and self-conjugate sets of m.o.l.s., Ann. Discrete Math. 15 (1982), 143–159.

[65] A.D. Forbes, M.J. Grannell, T.S. Griggs, New type B colorable S(2, 4, v) designs, J. Combin. Designs 15 (2007), 357–368.

[66] A.D. Forbes, M.J. Grannell, T.S. Griggs, The design of the century, Math. Slovaca 57 (2007), 495–499.

[67] F. Franek, T.S. Griggs, C.C. Lindner, A. Rosa, Completing the spectrum of 2chromatic S(2, 4, v), Discrete Math. 247 (2002), 225–228.

[68] H.L. Fu, Steiner quadruple systems with a spanning block design, Congr. Numer. 60 (1987), 145–150.

[69] R. Fuji-Hara, Y. Miao, Optical orthogonal codes: their bounds and new optimal constructions, IEEE Trans. Inform. Theory 46 (2000), 2396–2406.

[70] R. Fuji-Hara, Y. Miao, J.X. Yin, Optimal (9v, 4, 1) optical orthogonal codes, SIAM J. Discrete Math. 14 (2001), 256–266.

[71] R. Fuji-Hara, S.A. Vanstone, Transversal designs and doubly-resolvable designs, Europ. J. Combin. 1 (1980), 219-223.

[72] R. Fuji-Hara, S.A. Vanstone, Mutually orthogonal resolutions from finite geometries, Ars Combin. 12 (1981), 189–207.

[73] R. Fuji-Hara, S.A. Vanstone, Orthogonal resolutions of lines in AG(n, q), Discrete Math. 41 (1982), 17–28.

[74] B. Ganter, Endliche Vervollständigung partieller Steinerscher Systeme, Archiv Math. 22 (1971), 328–332.

[75] B. Ganter, Partial pairwise balanced designs, Teorie Combinatorie II, Colloq. Internaz. Roma 1973, Atti dei Convegni Lincei 17 Accad. Naz. dei Lincei, Roma, 1976, pp. 3776–380.

[76] B. Ganter, R. Metz, Kombinatorische Algebra: Koordinatisierung von Block plänen, Beiträge zur geometrischen Algebra, Proc. Sympos. Duisburg 1976, Birkhäuser, Basel, 1977 pp. 111–124.

[77] B. Ganter, J. Pelikán, L. Teirlinck, Small sprawling systems of equicardinal sets, Ars Combin. 4 (1977), 133–142.

[78] B. Ganter, H. Werner, Equational classes of Steiner systems, Alg. Univ. 5 (1975), 125–140.

[79] B. Ganter, H. Werner, Equational classes of Steiner systems II., Proc. Conf. Alg. Aspects Combinatorics, Toronto 1975, Congr. Numer. XIII, Utilitas Math. Publ. Inc., Winnipeg, 1975, pp. 283–285.

[80] B. Ganter, H. Werner, Co-ordinatizing Steiner systems, Ann. Discrete Math. 7 (1980), 3–24.

[81] G. Ge, M. Greig, A.C.H. Ling, R.S. Rees, Resolvable balanced incomplete block designs with subdesigns of block size 4, Discrete Math. 308 (2008), 2674–2703.

[82] G. Ge, C.W.H. Lam, A.C.H. Ling, H. Shen, Resolvable maximum packing with quadruples, Des. Codes Cryptogr. 35 (2005), 287–302.

[83] L. Gionfriddo, A conjecture of Berge about linear hypergraphs and Steiner systems S(2, 4, v), Discrete Math. 255 (2002), 125–133.

[84] M. Gionfriddo, L. Milazzo, A. Rosa, V. Voloshin, Bicolouring Steiner systems S(2, 4, v), Discrete Math 283 (2004), 249–253.

[85] D.A. Grable, K.T. Phelps, Random methods in design theory: a survey, J. Combin. Designs 4 (1996), 255–273.

[86] D.A. Grable, K.T. Phelps, V. Rödl, The minimum independence number for designs, Combinatorica 15 (1995), 175–185.

[87] M.J. Grannell, T.S. Griggs, Product constructions for cyclic block designs II. Steiner 2-designs, J. Combin. Theory (A) 42 (1986), 179–183.

[88] M. Greig, A. Rosa, Maximal arcs in Steiner systems S(2, 4, v), Discrete Math. 267 (2003), 143–151.

[89] H. Gropp, The elementary abelian Steiner systems S(2, 4, 49), Discrete Math. 64 (1987), 87–90.

[90] H. Gropp, “Il metodo di Martinetti” (1887) or Configurations and Steiner systems S(2, 4, 25), Ars Combin. 24B (1987), 179–188.

[91] M. Hall Jr., Combinatorial Theory,, Second Edition, J. Wiley, 1986.

[92] H. Hanani, The existence and construction of balanced incomplete block designs, Ann. Math. Stat. 32 (1961), 361–386.

[93] H. Hanani, Balanced incomplete block designs and related designs, Discrete Math. 11 (1975), 255–369.

[94] H. Hanani, D.K. Ray-Chaudhuri, R.M. Wilson, On resolvable designs. Discrete Math. 3 (1972), 343–357.

[95] A. Hartman, K.T. Phelps, Steiner quadruple systems Contemporary Design Theory. A Collection of Surveys, (Ed. J.H. Dinitz, C.J. Colbourn), J. Wiley, 1992, pp. 205– 240.

[96] J.W.P. Hirschfeld, Projective Geometries over Finite Fields, 2nd Ed., Oxford Univ. Press, 1998.

[97] D.G. Hoffman, C.C. Lindner, K.T. Phelps, Blocking sets in designs with block size 4, Europ. J. Combin. 11 (1990), 451–457.

[98] P. Horák, A. Rosa, Decomposing Steiner triple systems into small configurations, Ars Combin. 26 (1988), 91–105.

[99] J.D. Horton, R.C. Mullin, R.G. Stanton, Minimal coverings of pairs by quadruples, Proc. 2nd Louisiana Conf. Combinatorics, Graph Theory and Computing, Lousiana State Univ., Baton Rouge, 1971, pp. 495–516.

[100] L. Ji, L. Zhu, Construction for Steiner quadruple systems with a spanning block design, Discrete Math. 261 (2003), 347–360.

[101] M. Jimbo, A recursive construction of 1-rotational Steiner 2-designs, Aequat. Math. 26 (1983), 184–190.

[102] M. Jimbo, Cyclic neofields and cyclic Steiner 2-designs with block size 4, Europ. J. Combin. 4 (1983), 247–254.

[103] M. Jimbo, Recursive constructions for cyclic BIB designs and their generalizations, Discrete Math. 116 (1993), 79–95.

[104] M. Jimbo, S. Kuriki, On a composition of cyclic 2-designs, Discrete Math. 46 (1983), 249–255.

[105] M. Jimbo, S.A. Vanstone, Recursive constructions for resolvable and doubly resolvable 1-rotational Steiner 2-designs, Utilitas Math. 26 (1984), 45–61.

[106] S. Kageyama, Y. Miao, Note on a paper “1-rotational designs with block size 4” Bull. Inst. Combin. Appl. 20 (1997), 82–84.

[107] P. Kaski, P.R.J., Östergård, Classification Algorithms for Codes and Designs, Springer, 2006.

[108] P. Kaski, P.R.J., Östergård, Classification of resolvable balanced incomplete block designs - the unitals on 28 points, Math. Slovaca 59 (2009), 121–136.

[109] E.S. Kramer, S.S. Magliveras, R. Mathon, The Steiner systems S(2, 4, 25) with nontrivial automorphism group, Discrete Math. 77 (1989), 137–157.

[110] E.S. Kramer, S.S. Magliveras, V.D. Tonchev, On the Steiner systems S(2, 4, 25) invariant under a group of order 9, Ann. Discrete Math. 34 (1987), 307–314.

[111] V. Krčadinac, Steiner 2-designs S(2, 4, 28) with nontrivial automorphisms, Glasnik Mat. 37(57) (2002), 259–268.

[112] V. Krčadinac, Some new Steiner 2-designs S(2, 4, 37), Ars Combin. 78 (2006), 127– 135.

[113] C. Lam, Y. Miao, M. Mishima, Cyclically resolvable cyclic Steiner 2-systems S(2, 4, 52), J. Stat. Plann. Infer. 95 (2001), 245–256.

[114] E.R. Lamken, Designs with mutually orthogonal resolutions and decompositions of edge-colored graphs, J. Combin. Designs 17 (2009), 425–447.

[115] E.R. Lamken, W.H. Mills, R.S. Rees, Resolvable minimum coverings with quadruples, J. Combin. Designs 6 (1998), 431–451.

[116] E.R. Lamken, R.M. Wilson, Decomposition of edge-colored complete graphs, J. Combin. Theory (A) 89 (2000), 149–200.

[117] H. Li, On block-transitive 2 − (v, 4, 1)-designs, J. Combin. Theory (A) 69 (1995), 115-124.

[118] Y.S. Liaw, 1-rotational designs with block size 4 Bull. Inst. Combin. Appl. 13 (1995), 91–98.

[119] C.C. Lindner, Embedding block designs into resolvable block designs, Ars Combin. 1 (1976), 215–219.

[120] C.C. Lindner, How to construct a block design with block size four admitting a blocking set, Australas. J. Combin. 1 (1990), 101–125.

[121] C.C. Lindner, M. Meszka, A. Rosa, On a problem of Lo Faro concerning blocking sets in Steiner systems S(2, 4, v), Congr. Numer. 174 (2005), 23–27.

[122] C.C. Lindner, A. Rosa, Steiner quadruple systems - a survey, Discrete Math. 21 (1978), 147–181.

[123] C.C. Lindner, A. Rosa, The metamorphosis of λ-fold block design with block size four into λ-fold triple systems, J. Statist. Pl. Infer. 106 (2002), 69–76.

[124] V. Linek, E.B. Wantland, Coloring BIBDs with block size 4, J. Combin. Designs 6 (1998), 403–409.

[125] A.C.H. Ling, Hyperovals in Steiner systems, J. Geometry 77 (2003), 129–135.

[126] G. Lo Faro, Sui blocking sets nei sistemi di Steiner S(2, 4, v), Boll. Un. Mat. Ital (VII) A − 4 (1990), 71–76.

[127] R. Mathon, Constructions for cyclic Steiner 2-designs, Ann. Discrete Math. 34 (1987), 353–362.

[128] R. Mathon, Seaching for spreads and packings, Geometry, Combinatorial Designs and Related Structures, Proc. 1st Pythag. Conf., Cambridge Univ. Press, 1997, pp. 161–176.

[129] R. Mathon, A. Rosa, 2-(v, k, λ) designs of small order Handbook of Combinatorial Designs, 2nd Edition (Ed. C.J. Colbourn, J.H. Dinitz), CRC Press, Boca Raton, 2007, pp. 25–58.

[130] R. Mathon, S.A. Vanstone, Doubly resolvable Kirkman systems, Congr. Numer. 29 (1980), 611–625.

[131] M. Meszka, Private communication

[132] M. Meszka, A.Rosa, Embedding Steiner triple systems into Steiner systems S(2, 4, v), Discrete Math. 274 (2004), 199–212.

[133] L. Milazzo, Z. Tuza, A class of Steiner systems S(2, 4, v) with arcs of extremal size, Tatra Mt. Math. Publ. 36 (2007), 153–162.

[134] S. Milici, A. Rosa, V. Voloshin, Colouring Steiner systems with specified block colour patterns, Discrete Math. 240 (2001), 145–160.

[135] W.H. Mills, On the covering of pairs by quadruples I, J. Combin. Theory (A) 13 (1972), 55–78.

[136] W.H. Mills, On the covering of pairs by quadruples II, J. Combin. Theory (A) 15 (1973), 138–166.

[137] W.H. Mills, R.C. Mullin, Coverings and packings, Contemporary Design Theory. A Collection of Surveys (Ed. J.H. Dinitz, D.R. Stinson), Wiley, 1992, pp. 371–399.

[138] K. Momihara, Strong difference families, difference covers, and their applications for relative difference families, Des. Codes Cryptogr. 51 (2009), 253–273.

[139] E.H. Moore, Tactical memoranda I-III, Amer. J. Math. 18 (1896), 264–303.

[140] R.C. Mullin, C.C. Lindner, Lower bounds for maximal partial parallel classes in Steiner systems, J. Combin. Theory (A) 26 (1979), 314-318.

[141] W. Neidhardt, Blocking sets in S(2, 4, v), Mitt. Math. Sem Giessen 201, (1991), 133–140.

[142] J. Nešetřil, V. Rödl, Strong Ramsey theorems for Steiner systems, Trans. Amer. Math. Soc. 303 (1987), 183–192.

[143] S. Niven, On the number of k-tuples in maximal systems m(k, l, n),, Combinatorial Structures and their Applications, Proc. Conf. Calgary 1969, Gordon and Breach, New York, 1970, pp. 303–306.

[144] J. Novák, Packings of pairs with a minimum known number of quadruples, Math. Bohemica 120 (1995), 367–377.

[145] L.P. Petrenjuk, A.J. Petrenjuk, O neizomorfnykh B(25, 4, 1) i KST(21), Kirovo- gr. Inst. S.-Kh. Mašinostr., Kirovograd, 1983, pp. 1–9

[146] A.J. Petrenjuk, Ob odnom semeistve invariantov i novykh neizomorfnykh skhemakh B(28, 4, 1), Kirovogr. Inst. S.-Kh. Mašinostr., Kirovograd, 1984, pp. 1–28.

[147] K.T. Phelps, A note on partial S(s − 1, s + 1, v) subsystems of a S(s, s + 1, v), Proc. 9th S.-E. Conf. Combin., Graph Theory and Computing, Boca Raton 1978, Congr. Numer. XXI, Utilitas Math., 1978, pp. 581–586.

[148] K.T. Phelps, Halving block designs with block size four, Australas. J. Combin. 3 (1991), 231–234.

[149] K.T. Phelps, M.J. de Resmini, Partitioning twofold triple systems into complete arcs, Discrete Math. 104 (1992), 273–280.

[150] K. Pukanow, On the number of nonisomorphic configurations C(4, 2, 1, v), Prace Naukowe Inst. Mat. Fiz. Teoret. Politechn. Wroclaw, No.9, Wroclaw, 1973, pp. 45– 47.

[151] K. Pukanow, On number of nonisomorphic block systems B(4, 1, v), Prace Naukowe Inst. Mat. Politechn. Wroclaw, No.12, Wroclaw, 1976, pp. 11–37.

[152] R.W. Quackenbush, Near vector spaces over GF(q) and (v, q + 1, 1)-BIBD’s, Lin. Alg. Appl. 10 (1975), 259–266.

[153] R.W. Quackenbush, Algebraic speculations about Steiner systems, Ann. Discrete Math. 7 (1980), 25–35.

[154] R. Rees, D.R. Stinson, On combinatorial designs with subdesigns, Discrete Math. 77 (1989), 259–279.

[155] R. Rees, D.R. Stinson, On the existence of incomplete block designs of block size four having one hole, Utilitas Math. 35 (1989), 119–152.

[156] M.J. de Resmini, On k-sets of type (m, n) in a Steiner system S(2, 4, v), Finite Geometries and Designs, Proc. Conf. Chelwood Gate 1980, London MS Lecture Note Ser. 49, Cambridge Univ. Press, 1981, pp. 104–113.

[157] M.J. de Resmini, There exist at least three non-isomorphic S(2, 4, 28)’s, J. Geometry 16 (1981), 148–151.

[158] M.J. de Resmini, On sets of type (m, n) in BIBD’s with λ ⩾ 2, Ann. Discrete Math. 14 (1982), 183–206.

[159] M.J. de Resmini, On complete arcs in Steiner systems S(2, 3, v) and S(2, 4, v), Discrete Math. 77 (1989), 65–73.

[160] M.J. de Resmini, Some naive constructions of S(2, 3, v) and S(2, 4, v), Discrete Math. 97 (1991), 149–153.

[161] M.J. de Resmini, Some partitions of S(2, 3, v^{2}) and S(2, 4, v^{2}), Australas. J. Combin. 10 ( 1994), 289–291.

[162] M.J. de Resmini, K.T. Phelps, On some complete arcs in 2 − (v, 4, 1)-designs, J. Geometry 53 (1995), 20–20.

[163] C.A. Rodger, Linear spaces with many small lines, Discrete Math. 129 (1994), 167– 180.

[164] C.A. Rodger, E. Wantland, K. Chen, L. Zhu, Existence of certain skew Room frames with applications to weakly 3-chromatic linear spaces, J. Combin. Designs 2 (1994), 311–332.

[165] V. Rödl, E. Šiňajová, Note on independent sets in Steiner systems, Random Str. Alg. 5 (1994), 183–190.

[166] B. Rokowska, A new construction of the block systems B(4, 1, 25) and B(4, 1, 28), Colloq. Math. 38 (1977), 165–167.

[167] A. Rosa, Blocking sets and colourings in Steiner systems S(2, 4, v), Le Matematiche (Catania) 59 (2004), 341–348.

[168] A. Rosa, C.J. Colbourn, Colorings of block designs, Contemporary Design Theory. A Collection of Surveys (Ed. J.H. Dinitz, D.R. Stinson), Wiley, 1992, pp. 401–430.

[169] U. Rost, Untersuchung einer speziellen Klasse von Polyquasigruppen mittels (2, 4, v)-Steinersystemen, Fachtagung “Algebra und Graphentheorie”, Siebenlein, 1985, pp. 61–64.

[170] U. Rost, F. Walther, Steinersysteme und Polyquasigruppen, Wiss. Z. Pädag. Hochschule “Karl Friedrich Wilhelm Wander” Dresden 19 (1985), 57–63.

[171] A. Samardžiski, A contruction of 2−(v, 4, 1)-design, God. Zb. Mat. Fak. Univ. Kiril Metodij Skopje 28 (1977), 39–49.

[172] J. Schönheim, On coverings, Pacific J. Math. 14 (1964), 1405–1411.

[173] J. Schönheim, On maximal systems of k-tuples, Studia Sci. Math. Hungar. 1 (1966), 363–368.

[174] N.V. Semakov, B.A. Zinoviev, Soveršennyye i kvazisoveršennyye ravnovesnyye kody, Problemy Peredač Informacii 5, 2 (1969), 14–18.

[175] H. Shen, On the existence of nearly Kirkman systems, Ann. Discrete Math. 52 (1992), 511–518.

[176] H. Shen, H. Zeitler, Systems S(2, 4, v) with exactly one or without any maximal subsystem, J. Geometry 57 (1996), 114–119.

[177] J. Shiftar, H. Zeitler, Special quasigroups and Steiner systems Nearrings, Near- fields and K-Loops, (Ed. G. Saad, M.J. Thomsen), Kluwer, 1997, pp. 403–416.

[178] E. Spence, The complete classification of Steiner systems S(2, 4, 25), J. Combin. Designs 4 (1996), 295–300.

[179] R.G. Stanton, Note on a construction for a (25, 4, 1) design, J. Combin. Math. Combin. Comput. 5 (1989), 61–62.

[180] R.G. Stanton, D.W. Kroecker, Another construction for the (25, 4, 1) design, J. Combin. Math. Combin. Comput. 18 (1995), 167–169.

[181] S.K. Stein, Homogeneous quasigroups, Pacific J. Math. 14 (1964), 1091–1102.

[182] D.R. Stinson, Determination of a packing number, Ars Combin. 3 (1977), 89–114.

[183] D.J. Street, J. Seberry, All DBIBDs with block size four exist, Utilitas Math. 18 (1980), 27–34.

[184] L. Szamkolowicz, On the problem of existence of finite regular planes, Colloq. Math. 9 (1962), 245–250.

[185] L. Teirlinck, Some new 2-resolvable Steiner quadruple systems, Des. Codes Cryptogr. 4 (1994), 5–10.

[186] V.D. Tonchev, The 3-ranks of the cyclic Steiner 2 − (40, 4, 1) designs, C.R. Acad. Bulg. Sci. 37 (1984), 1467–1469.

[187] V.D. Tonchev, Two new Steiner systems S(2, 4, 25), C.R. Acad. Bulg. Sci. 39 (1986), 47–48.

[188] V.D. Tonchev, A characterization of the Hermitian and Ree unitals of order 3, 5th Internat. Workshop on Algebr. and Combin. Coding Theory, Sozopol 1996, Shumen, 1996, pp. 270–279.

[189] V. Voloshin, On the upper chromatic number of a hypergraph, Australas. J. Combin. 11 (1995), 25–45.

[190] R. Wei, L. Zhu, Embeddings of Steiner systems S(2, 4, v), Ann. Discrete Math. 34 (1987), 465–470.

[191] R. Wei, L. Zhu, Embeddings of S(2, 4, v), Europ. J. Combin. 10 (1989), 201–206.

[192] M. Wojtas, On non-isomorphic balanced incomplete block designs B(4, 1, v), Colloq. Math. 35 (1976), 327–330.

[193] J.X. Yin, Some combinatorial constructions for optical orthogonal codes, Discrete Math. 185 (1998), 210–219.

[194] J.X. Yin, A general construction for optimal cyclic packing designs, J. Combin. Theory (A), 97 (2002), 272–284.

[195] H. Zeitler, About near-resolvable systems S(2, 4, v), J. Combin. Inf. Syst. Sci. 15 (1990), 198–203.

[196] H. Zeitler, Über Steiner-Systeme S(4, v), Rad. Jugosl. Akad. Znan. Umjet., Mat. Znan. 450(9) (1990), 161–168.

[197] H. Zeitler, About special classes of Steiner systems S(2, 4, v), Discrete Math. 97 (1991), 399–407.

[198] H. Zeitler, About the number of maximal subsystems in S(2, 4, v), Matematiche (Catania) 48 (1993), 235–251.

[199] H. Zeitler, Special systems S(2, 4, v) with maximal subsystems, Glasnik Mat. 28(48) (1993), 191–207.

[200] H. Zeitler, Steiner-Systeme und Stein-Quasigruppen, Results Math. 25 (1994), 153– 165.