Combinatorics

Section 17.3 Constructing designs, and existence of designs

There are a number of nice methods for constructing designs. We will discuss some of these methods in this section. For some of them, you must start with one design, and use it to create a different design.

Method 1: Repeating blocks

This is probably the easiest, and (not surprisingly) the least useful of our construction methods.

Start with a BIBD\((v,k,\lambda)\text{.}\) For each block of the design, create \(t\) copies of that block. The result will be a BIBD\((v,k,t\lambda)\text{.}\)

Method 2: Taking the complement

This method also requires starting with a design. Start with \((V, \mathcal B)\text{,}\) a BIBD\((v,k,\lambda)\text{.}\)

Replace each block \(B \in \mathcal B\) with its complementary block, \(B^c=V\setminus B\text{.}\) Then

is a design.

The proof of this proposition is left to the reader, as Exercise 17.3.9.1.

Method 3: Cyclic designs

Suppose we have a difference collection for \(v\) with multiplicity \(\lambda\text{,}\) in which each set \(D_1, \ldots, D_m\) has the same cardinality. Use \(D_i+\ell\) to denote the set

performing the modular arithmetic so as to ensure that \(D_i+\ell \subseteq\{1, \ldots, v\}\text{.}\) Then the sets

form a BIBD\((v,|D_1|,\lambda)\) (hence our use of the symbol \(\lambda\) for the multiplicity).

In the above example, taking the \(57\) sets \(\{1,2,5\}+\ell\text{,}\) \(\{1,3,10\}+\ell\text{,}\) and \(\{1,7,15\}+\ell\text{,}\) where \(0\le \ell \le 18\text{,}\) gives a BIBD\((19,3,1)\text{.}\)

A design created using this method is called a cyclic design.

Notice that for a cyclic design to exist, since each set in the difference collection leads to \(v\) blocks in the final design, \(b\) must be a multiple of \(v\text{.}\)

Although these methods can successfully create designs with many different sets of parameters, they are not nearly enough to allow us to determine the parameters for which BIBDs exist. We noted previously that the necessary conditions given in Theorem 17.1.9 are not sufficient to guarantee the existence of a BIBD with a particular set of parameters. However, there is a very powerful result along these lines, known as Wilson's Theorem after its discoverer, Richard Michael Wilson (1945—). It tells us that if we fix \(k\text{,}\) there are only finitely many values for \(v\) that satisfy the necessary conditions but for which no BIBD\((v,k,1)\) exists. Then by Method 1 (repeating blocks), if a BIBD\((v,k,1)\) exists, then so does a BIBD\((v,k,\lambda)\) for any \(\lambda\text{.}\) Here is a formal statement of Wilson's Theorem.

We will not give a proof of this theorem.