Combinatorics

Section 17.2 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.2.8.1.

Method 3: Cyclic designs

This method may be easiest to think of in terms of the associated graph colouring. There are various more complicated versions of this construction that enable us to construct additional designs, but for the purposes of this course, we will focus on almost the most basic version. This most basic version unfortunately gets confusing when \(v\) is even, so we will only use it here when \(v\) is odd.

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{.}\)

Let's go over this construction again, thinking about the graph version of the problem. For simplicity, we'll look only at the special case \(\lambda=1\text{.}\) So our object is to colour the edges of the complete graph \(K_v\) so as to ensure that every colour class is a \(K_k\text{.}\) If we draw the vertices of the graph in a circle, and think of the length of an edge as being one more than the number of vertices between its endvertices as you travel around the circle in whichever direction is shorter, then for every possible length between \(1\) and \((v-1)/2\text{,}\) \(K_v\) has \(v\) edges of that length. (This is where the trouble arises if \(v\) is even: there are only \(v/2\) edges of length \(v/2\text{.}\)) Furthermore, if we rotate any edge by one step around the graph (i.e. move both of its endpoints one step in the same direction) repeatedly, after \(v\) such rotations we will have moved the edge onto every other edge of that length.

These ideas demonstrate that if we can come up with a set of \(K_k\)s, such that every edge length appears in exactly one of the \(K_k\)s, then by taking each one of these as well as every possible rotation of each one of these, as a colour class, we find our desired edge-colouring of \(K_v\text{.}\)

A picture is worth a thousand words. The example above is equivalent to edge-colouring \(K_{19}\) so that every colour class forms a \(K_3\text{,}\) since \(v=19\) and \(k=3\text{.}\) The edge lengths in \(K_{19}\) are \(\{1, \ldots, 9\}\text{.}\) We will show three \(K_3\)s, such that every edge length from \(\{1, \ldots, 9\}\) appears in exactly one of them. By rotating each of them, giving each rotation a new colour, we obtain \(57\) \(K_3\)s that use every edge of \(K_{19}\) exactly once. We've labeled the vertices \(1\) through \(19\) to make the edge lengths easier to work out. To enable this to be understood in black-and-white, instead of drawing actual colours on the edges we will draw solid edges for blue, dotted edges for red, and dashed edges for green.

The solid (or blue) triangle has edges of lengths \(1\text{,}\) \(3\text{,}\) and \(4\text{;}\) the dotted (or red) triangle has edges of lengths \(2\text{,}\) \(7\text{,}\) and \(9\text{;}\) and the dashed (or green) triangle has edges of lengths \(6\text{,}\) \(8\text{,}\) and \(5\text{.}\)

A design created using this method is called a cyclic design, since a small number of “starter blocks” are being rotated cyclically (in the graph) to find the remaining blocks of the 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.