RETRACTED ARTICLE: Constructions for t-designs and s-resolvable t-designs

Constructions of simple t-designs are a central theme in t-design theory. Several major approaches to the problem could be found in the literature such as the use of a possible automorphism group, the construction of large sets and the recursive construction methods. Automorphism group methods often need the use of computers to deal with huge combinatorial problems. For example, in 1982 Magliveras and Leavitt showed in a pioneer work the existence of the first non-trivial simple 6-designs by using groups [27]. Another way of dealing with methods by means of groups is to carry out group-theoretic arguments by using the knowledge of the group structures only. Actually, a great deal of simple t-designs are obtained by using groups, either through computer-based approaches [6, 7, 20, 21, 23, 24] or through group-theoretic arguments [3‐5, 9‐11, 13, 16, 30]. In a seminal paper in 1987 [31] Teirlinck proved the existence of non-trivial simple t-designs for arbitrarily large t by constructing large sets. This achievement strongly motivates numerous researchers to develop further this part of t-design theory [1, 18, 19, 22, 25, 26, 39]. Recursive methods appear to be a vital element for the study of t-designs. Normally, statements obtained by recursive approaches are of general nature and do not limit on values of t [28, 33‐38].

In the present paper we introduce recursive methods for constructing t-designs, s-resolvable t-designs and large sets of t-designs. In fact, the results reveal a remarkable connection between the ‘starting’ and ‘resulting’ designs, and therefore, they are very useful. For example, they allow us to construct large sets of t-designs for arbitrarily large t which were not known before.

We recall some basic notation and definitions which are used in the remaining sections. A t-design, denoted by t-\((v,k,\lambda )\), is a pair \((X, {{\mathcal {B}}})\), where X is a v-set of points and \({{\mathcal {B}}}\) is a collection of k-subsets of X, called blocks, such that every t-subset of X is a subset of exactly \(\lambda \) blocks, and \(\lambda \) is called the index of the design. A t-design is called simple if no two blocks are identical, otherwise, it is called non-simple. A t-(v, k, 1) design is called a Steiner t-design. The necessary conditions for the existence of a t-\((v,k,\lambda )\) design are thatare integers. Equivalently,orIf these divisibility conditions for \(t,\,k,v,\lambda \) are satisfied, we may say for short that the parameters t-\((v,k,\lambda )\) are admissible. The smallest positive integer \(\lambda \) for which these necessary conditions are satisfied is denoted by \(\lambda _\textrm{min}(t,k,v)\) or simply \(\lambda _\textrm{min}\). If \({{\mathcal {B}}}\) is the set of all k-subsets of X, then \((X, {{\mathcal {B}}})\) is a t-\((v,k, \lambda _\textrm{max})\) design, called the complete design, where \(\lambda _\textrm{max}={v-t \atopwithdelims ()k-t}\). If we complement each block of a t-\((v,k,\lambda )\) design with respect to the point set X, we get a t-\((v, v-k, \lambda ^*)\) design with \(\lambda ^*=\lambda \left( {\begin{array}{c}v-k\\ t\end{array}}\right) /\left( {\begin{array}{c}k\\ t\end{array}}\right) \), hence we usually assume \(k \le v/2.\) Moreover, if there is a t-\((v,k,\lambda )\) design, then \(\lambda _\textrm{min}\) divides \(\lambda \); and we normally assume that \(\lambda \le \lambda _\textrm{max}/2\).

A t-\((v,k,\lambda )\) design \((X, {{\mathcal {B}}})\) is called s-resolvable, for \(1\le s \le t-1\), if the block set \( {{\mathcal {B}}}\) can be partitioned into \(N \ge 2\) disjoint classes \({{\mathcal {B}}}_1, \ldots , {{\mathcal {B}}}_N\) such that each \((X,{{\mathcal {B}}}_i)\) is an s-\((v,k,\delta )\) design, for \(i=1,\ldots , N\). Each \({{\mathcal {B}}}_i\) is called an s-resolution class or simply a resolution class. It is also said that \((X, {{\mathcal {B}}})\) has an s-resolution; obviously \(N= \lambda _s/\delta \). The necessary conditions for a t-\((v,k,\lambda )\) design to be s-resolvable are thatIf the complete k-(v, k, 1) design can be partitioned into N disjoint t-\((v,k,\lambda )\) designs, for \(t < k\), then it is said that there is a large set of t-\((v,k,\lambda )\) designs, denoted by LS[N](t, k, v), or \(LS_{\lambda }(t,k,v)\). All designs in this paper are assumed to be simple. When the discussion concerns non-simple t-designs, this will be stated explicitly.

Let \((Z, {{\mathcal {B}}})\) be a simple t-\((v,k,\lambda )\) design, where \(Z=\{1, \ldots , v\}\). Let \(X= Z \cup \{v+1\} = \{1, \ldots , v, v+1\}\). Define \(Z_i=X \setminus \{i\}\) for \(i=1, \ldots , v+1\). In particular, \(Z_{v+1}=Z\). Let \((Z_i, {{\mathcal {B}}}_i)\) be a copy of \((Z, {{\mathcal {B}}})\) defined on the point set \(Z_i=\{1, \ldots , i-1, i+1, \ldots , v+1\}\) for \(i=1, \ldots , v+1\); note that \((Z_{v+1}, {{\mathcal {B}}}_{v+1}) = (Z, {{\mathcal {B}}})\). For a given \(i=1, \ldots , v\), the blocks of \({{\mathcal {B}}}_i\) are obtained from those of \({{\mathcal {B}}}_{v+1}\) as follows. Let \(B=\{i_1, i_2, \ldots , i_k\} \in {{\mathcal {B}}}_{v+1}\). For each \(i \in X\), defineandWe claim that \((X, {{\mathcal {D}}})\) is a t-\((v+1, k+1, \Lambda ^*)\) design with repeated blocks, where \(\Lambda ^* = \lambda \frac{v+1-t}{k+1-t}(k+1)\), and each block of \({{\mathcal {D}}}\) is repeated \((k+1)\) times. Let \(T=\{i_1, \ldots , i_t\}\) be a t-subset of X. The two cases 1. and 2. giveas desired.

Next we show that \((X, {{\mathcal {D}}})\) has repeated blocks and each block of \({{\mathcal {D}}}\) is repeated \((k+1)\) times. Without loss of generality consider a block \(D=\{v+1\} \cup B \in {{\mathcal {D}}}_{v+1}\), where \(B=\{i_1, \ldots , i_k\} \in {{\mathcal {B}}}_{v+1}\). Because \((Z_i, {{\mathcal {B}}}_i)\) is a copy of \((Z_{v+1}, {{\mathcal {B}}}_{v+1})\), \(i=1, \ldots , v\), we see thatIt follows that the \((k+1)\) blocksare identical. These blocks are the only repeated blocks of D. This can be seen as follows. If \(D'\) is a repeated block of D, then \(D'\) must be of the form \(D'=\{j\}\cup B\) with \(B\in {{\mathcal {B}}}_j\) for a \(j\in \{i_1,\ldots , i_k, v+1 \}\), say \(j=i_h\). But since any two blocks in \({{\mathcal {D}}}_{j_h}\) are distinct, so \(D'=D_{j_h}\), where \(D_{j_h}\) is one of the \((k+1)\) repeated blocks of D described above. Hence, \((X, {{\mathcal {D}}})\) is a non-simple t-\((v+1, k+1,\lambda \frac{v+1-t}{k+1-t}(k+1))\) design, in which any block is repeated \((k+1)\) times, which proves the claim. Define \(\Lambda = \lambda \frac{v+1-t}{k+1-t}.\) Now assume that the conditionsare satisfied, then by removing the repeated blocks of \((X, {{\mathcal {D}}})\) we obtain a simple t-\((v+1,k+1, \Lambda )\) design \((X, {{\mathcal {C}}})\). Note that the conditions in (1) are the necessary conditions for the existence of \((X, {{\mathcal {C}}})\). A close look shows that the conditions in (1) are already satisfied for \(1\le i\le t\), because these cases coincide with the divisibility conditionsfor the t-\((v,k, \lambda )\) design \((Z, {{\mathcal {B}}})\), which are assumed to be satisfied. Consequently, the conditions in (1) are fulfilled, if for \(i=0\) we haveor equivalently,is an integer. Hence we have proved the following theorem.

In Theorem 2.1, if \(\lambda \left( {\begin{array}{c}v+1\\ k+1\end{array}}\right) / \left( {\begin{array}{c}v-t\\ k-t\end{array}}\right) \) is an integer, then we simply say that the parameters t-\((v+1,k+1,\Lambda )\) with \(\Lambda =\lambda \frac{v+1-t}{k+1-t}\) are admissible. Equivalently, \(\Lambda \) is a multiple of \(\lambda _{\text {min}}(t,k+1,v+1).\)

The following examples illustrate Theorem 2.1.

We keep the notation from the previous section. Now assume that the t-\((v,k,\lambda )\) design \((Z, {{\mathcal {B}}})\) is s-resolvable. Let s-\((v,k,\delta _s)\) be the parameters of the designs in the resolution of \((Z, {{\mathcal {B}}})\), and let N be the number of resolution classes. Thus, the block set \({{\mathcal {B}}}\) can be written as \({{\mathcal {B}}}= {{\mathcal {B}}}^1 \cup \cdots \cup {{\mathcal {B}}}^N\), which is a partition of \({{\mathcal {B}}}\) into subsets \({{\mathcal {B}}}^j\) such that \((Z, {{\mathcal {B}}}^j)\) is an s-\((v,k,\delta _s)\) design for \(j=1, \ldots , N\). By Theorem 2.1\((X, {{\mathcal {D}}})\) is a non-simple t-\((v+1,k+1,\Lambda (k+1))\) design with \(\Lambda =\lambda \frac{v+1-t}{k+1-t}\), in which any block is repeated \((k+1)\) times. In particular, applying Theorem 2.1 to \((Z, {{\mathcal {B}}}^j)\), \(j=1, \ldots , N\), yields a non-simple s-\((v+1,k+1,\Delta _s(k+1))\) design \((X, {{\mathcal {D}}}^j)\) with \(\Delta _s=\delta _s\frac{v+1-s}{k+1-s}\), and any block is repeated \((k+1)\) times. It follows that there is a partition of \((X, {{\mathcal {D}}})\) into N disjoint non-simple s-designs \((X, {{\mathcal {D}}}^1), \ldots , (X, {{\mathcal {D}}}^N)\). Now assume that \(\lambda \left( {\begin{array}{c}v+1\\ k+1\end{array}}\right) / \left( {\begin{array}{c}v-t\\ k-t\end{array}}\right) \) is an integer. Again by Theorem 2.1, if the divisibility conditionsare satisfied, then by removing the repeated blocks of \((X, {{\mathcal {D}}}^j)\) we obtain a simple s-\((v+1,k+1,\delta _s\frac{v+1-s}{k+1-s})\) design \((X, {{\mathcal {C}}}^j)\) for \(j=1, \ldots , N.\) Thus, in this way, the non-simple design \((X, {{\mathcal {D}}})\) will yield a simple t-\((v+1,k+1,\Lambda )\) design \((X, {{\mathcal {C}}})\), which is resolvable into s-designs \((X, {{\mathcal {C}}}^j)\), \(j=1, \ldots , N.\) Moreover, the s-resolvability of \((Z,{{\mathcal {B}}})\) implies that \(N\delta _i =\lambda _i\) for \(0\le i\le s\), or equivalently,Thus the s-resolvability conditions in (3) for \((X, {{\mathcal {C}}})\) are equivalent toObserve that the conditions \(N\>\vert \> \Lambda _i \) for \(1\le i \le s\) are met, since they are identical to \(N\>\vert \> \lambda _j\) for \(0\le j \le s-1\), which are already satisfied by the assumption. Thus, the conditions \(N\>\vert \> \Lambda _i \hspace{5.0pt}\text {for} \hspace{5.0pt}0\le i \le s\) are satisfied, if \(N\>\vert \> \Lambda _0\), which is \(N\>\vert \> \lambda \left( {\begin{array}{c}v+1\\ k+1\end{array}}\right) / \left( {\begin{array}{c}v-t\\ k-t\end{array}}\right) .\) Hence, we have proved the following result.

The most important consequence of Theorem 3.1 is the following corollary.

It is appropriate to include a remark on the conditions in Theorem 3.1. The first condition requires that \(\lambda \left( {\begin{array}{c}v+1\\ k+1\end{array}}\right) / \left( {\begin{array}{c}v-t\\ k-t\end{array}}\right) \) is an integer and the second that N divides \(\lambda \left( {\begin{array}{c}v+1\\ k+1\end{array}}\right) / \left( {\begin{array}{c}v-t\\ k-t\end{array}}\right) .\) Thus, if the first condition is not satisfied, then neither is the second. However, if the first condition is fulfilled, then the second does not need to be met. The following example clarifies these cases and also shows an iterated use of Theorem 3.1.

Consider a Steiner 5-(84, 6, 1) design whose blocks are a union of 18 long block orbits of \(\text {PSL}_2(83)\), (i.e. orbits of length \(|\text {PSL}_2(83)|\)). The design is thus 3-resolvable with \(N=18\) resolution classes [8]. Applying Theorem 3.1 yields a 3-resolvable 5-\((85,7, 4\cdot 10)\) design, since both conditions are satisfied. By repeated application to this resulting 5-\((85,7, 4\cdot 10)\) design, we again get a 3-resolvable 5-\((86,8, 54\cdot 20)\) design. Now, by applying Theorem 3.1 to the 5-\((86,8, 54\cdot 20)\) design, we find that \(\lambda \left( {\begin{array}{c}v+1\\ k+1\end{array}}\right) / \left( {\begin{array}{c}v-t\\ k-t\end{array}}\right) =87\cdot 43\cdot 85\cdot 7\cdot 83\cdot 41 \) is an integer. Hence, we get a 5-\((87,9, 738\cdot 30)\) design. However, since \(N=18\) does not divide \(87\cdot 43\cdot 85\cdot 7\cdot 83\cdot 41\), the latter is not 3-resolvable.

Here is an example for Corollary 3.2. Consider an \(LS_1(2,4,16)= LS[91](2,4,16)\) constructed by Mathon [29]. Since \(91\>\vert \> \left( {\begin{array}{c}17\\ 5\end{array}}\right) \), Corollary 3.2 gives an \(LS_5(2,5,17)= LS[91](2,5,17)\). Note that \(5= \lambda _\textrm{min}(2,5,17)\). Again if we apply Corollary 3.2 to LS[91](2, 5, 17), we find that \(91\>\vert \> \left( {\begin{array}{c}18\\ 6\end{array}}\right) \). Hence there also exists an LS[91](2, 6, 18). It appears that LS[91](2, 5, 17) and LS[91](2, 6, 18) are unknown to date.

We should note that LS[91](2, 4, 16) is the second known large set of Steiner t-(v, k, 1) designs with \(t \ge 2\) and \(k \ge 4\); the first one is \(LS_1(2,4,13)= LS[55](2,4,13)\) [15, 17]. However, there is no LS[55](2, 5, 14), since these parameters are not admissible, in particular \(55\not \mid \left( {\begin{array}{c}14\\ 5\end{array}}\right) \).

Again we remark that the conditions of Theorems 2.1, 3.1 and Corollary 3.2 are simply the necessary divisibility conditions required for a t-design, or a t-design with resolution to exist. Generally, these necessary conditions are implicitly assumed, when the existence or the resolvability of a design is concerned. Hence, in this sense, the above theorems and corollary actually prove an intrinsic connection between the ‘starting’ and ‘resulting’ designs.

A few examples in the preceding sections have already suggested that the methods are useful. Actually, if applied fully, the results will produce infinitely many new t-designs, t-designs with s-resolutions, and large sets of t-designs. In this section, however, we limit our attention to some infinite series of t-designs for \(t \ge 4\), which are derived from Theorems 2.1, 3.1 and Corollary 3.2, as an assertion of their unexpected strength.

The paper introduces new recursive constructions for t-designs, s-resolvable t-designs including large sets of t-designs. The conditions required for the constructions are simply the necessary divisibility conditions for the considered designs, and the results turn out to be very effective. In particular, they reveal a remarkable link between the ‘starting’ and ‘resulting’ designs and appear to be significant to t-design theory. A full application of the results would certainly improve the number of known t-designs, s-resolvable t-designs and large sets of t-designs considerably.