17.1: Balanced Incomplete Block Designs (BIBD)

Suppose you have \(7\) possible treatments for a disease, that you hope may work well singly or in combination. You would like to try out every possible combination of them, but the number of (non-empty) subsets of the set of \(7\) treatments is \(2^7 − 1 = 127\), and you have only \(7\) mice in the lab who have this disease. You believe that using a pair of the treatments together will have a more significant impact than adding more of the treatments, but even trying every pair of treatments on a different mouse would require \(\binom{7}{2} = 21\) mice.

Here is a strategy you could try: give each of the mice \(3\) of the treatments, according to the following scheme. For \(1 ≤ i ≤ 7\), the treatments given to mouse \(i\) will be the elements of the \(i^{\text{th}}\) set in the following list

\[\{1, 2, 3\}, \{1, 4, 5\}, \{1, 6, 7\}, \{2, 4, 6\}, \{2, 5, 7\}, \{3, 4, 7\}, \{3, 5, 6\}\]

Careful perusal of this scheme will show that every pair of treatments is used together on precisely one of the mice.

Definition: Design and Block

A design is a pair \((V, \mathcal{B})\), where \(V\) is a finite set of points (varieties) and \(B\) is a collection of subsets of \(V\), called blocks of the design

This definition of a design is too broad to be of much interest without additional constraints, but a variety of different constraints have been studied.

Notation

We use \(v\) to denote \(|V|\) and \(b\) to denote \(|\mathcal{B}|\).

Definition: Regular, Uniform, and Balanced Design

A regular design is a design in which every point appears in the same number of blocks, \(r\).

A uniform design is a design in which every block contains the same number of points, \(k\).

A balanced design is a design in which every pair of points appear together in the same number of blocks, \(λ\).

Example \(\PageIndex{1}\)

In our disease treatments for the mice, we have \(V = \{1, 2, 3, 4, 5, 6, 7\}\)

\(\mathcal{B} = \{\{1, 2, 3\}, \{1, 4, 5\}, \{1, 6, 7\}, \{2, 4, 6\}, \{2, 5, 7\}, \{3, 4, 7\}, \{3, 5, 6\}\}.\)

This is a regular, uniform, balanced design. In this design, \(v = 7\), \(b = 7\), \(r = 3\), \(k = 3\), and \(λ = 1\).

A regular, uniform, balanced design may be referred to as a \((b, v, r, k, λ)\)-design. So our disease treatments for the mice formed a \((7, 7, 3, 3, 1)\)-design.

A \(b, v, r, k, λ)\)-design is called complete if \(v = k\). In this case, every block will contain every point. A \((b, v, r, k, λ)\)-design is called trivial if \(k = 1\). In this case, every block consists of a single point, and no points appear together in a block. The case \(k = 2\) is also fairly trivial since in this case, the blocks of the design must consist of the \(\binom{v}{2}\) pairs of elements of \(v\), each occurring \(λ\) times.

Definition: Balanced Incomplete Block Design (BIBD)

A balanced incomplete block design (BIBD) is a regular, uniform, balanced design that is not complete. So it is a \((b, v, r, k, λ)\)-design with \(k < v\).

Although this definition includes the possibility \(k = 1\) or \(k = 2\), these are not interesting cases, and can usually be ignored

Example \(\PageIndex{2}\)

Here is another BIBD. This one has parameters \((20, 16, 5, 4, 1)\).

\[\begin{equation} \begin{split} &\{a, b, c, d\}, &\;\;\{e, f, g, h\}, &\;\;\{i, j, k, l\}, &\;\;\{m, n, o, p\}, &\;\;\{a, e, i, m\}, &\;\;\{a, f, j, n\}, \;\;&\{a, g, k, o\},\\ &\{a, h, l, p\}, &\;\;\{b, e, j, o\}, &\;\;\{b, f, i, p\}, &\;\;\{b, g, l, m\}, &\;\;\{b, h, k, n\}, &\;\;\{c, e, l, o\}, \;\;&\{c, f, k, p\},\\ &\{c, g, i, n\}, &\;\;\{c, h, j, m\}, &\;\;\{d, e, k, n\}, &\;\;\{d, f, l, m\}, &\;\;\{d, g, j, p\}, &\;\;\{d, h, i, o\} \end{split} \end{equation}\]

Theorem \(\PageIndex{1}\)

If a \((b, v, r, k, λ)\)-design exists, then \(bk = vr\) and

\[r(k − 1) = λ(v − 1)\]

Proof

For the first equation, we count the total number of appearances of each point in the design (including repetitions) in two ways. This is another example of counting ordered pairs from a cartesian product, as we have discussed previously.

First, there are \(b\) blocks, each of which has \(k\) points in it. So the answer will be \(bk\).

Second, there are \(v\) points, each of which appears \(r\) times. So the answer will be \(vr\).

Thus, \(vr = bk\).

For the second equation, we fix a point \(p\) and count the number of points with which \(p\) appears in a block, in two ways.

First, \(p\) appears in \(r\) blocks. In each of these, there are \(k−1\) points besides \(p\). So the answer will be \(r(k − 1)\).

Second, for every point \(p' ∈ V\) with \(p' \neq p\), the point \(p'\) appears with \(p\) in \(λ\) different blocks. Since there are \(v − 1\) choices for \(p'\), the answer will be \(λ(v − 1)\)

Thus, \(r(k − 1) = λ(v − 1)\).

With a bit of calculation, the results of Theorem 17.1.1 tell us that

\[r = \dfrac{λ(v − 1)}{k −1} \label{17.1.4}\]

and

\[b = \dfrac{vr}{k} = \dfrac{λv(v − 1)}{k(k − 1)} \label{17.1.5}\]

Thus, if we know that a design is regular, uniform, and balanced, then the parameters \(r\) and \(b\) can be determined from the parameters \(v\), \(k\), and \(λ\). We therefore often shorten our notation and refer to a BIBD\((v, k, λ)\).

Theorem \(\PageIndex{2}\)

A BIBD\((v, k, λ)\) is equivalent to colouring the edges of the multigraph \(λK_v\) (the multigraph in which each edge of \(K_v\) has been replaced by \(λ\) copies of that edge) so that the edges of any colour form a \(K_k\).

Proof

Given an edge-colouring of \(λK_v\) as described, define the points of the design to be the set of vertices of the multigraph, and for each colour, create a block whose vertices are the vertices of the \(K_k\) that has that colour. All of these blocks will have cardinality \(k\). Every vertex has valency \(λ(v − 1)\), and every \(K_k\) of one colour that contains that vertex will use \(k − 1\) of the edges incident with that vertex, so every vertex will appear in

\[r = \dfrac{λ(v − 1)}{(k − 1)}\]

blocks. Now, any edge of the \(λK_v\) must appear in some \(K_k\) (the one coloured with the colour of that edge). Thus for any pair of points, these vertices are joined by \(λ\) edges each of which appears in some \(K_k\), so these points must appear together in \(λ\) of the \(K_k\) subgraphs, i.e \(λ\) of the blocks.

Similarly, given a BIBD\((v, k, λ)\), and a multigraph \(λK_v\), label the vertices of \(K_v\) with the points of the design. For each block of the design, use a new colour to colour the edges of a \(K_k\) that connects the points in that block. There will be enough uncoloured edges joining these points, since every pair of points appear together in exactly \(λ\) blocks, and there are \(λ\) edges joining the corresponding vertices. In fact, careful counting can show that this will result in colouring every edge of the multigraph.

This is nicest in the case where \(λ = 1\), when the BIBD corresponds to an edge-colouring of \(K_v\).

A colouring of the edges of a graph (or multigraph) is often referred to as a decomposition of the graph (or multigraph), since we can think of the colour classes as sets of edges whose union forms the entire edge set of the graph.

These provide alternate ways of thinking of designs that may be more intuitive, and are certainly more visual. Equations \ref{17.1.4} and \ref{17.1.5} lead to numerical conditions on \(v\), \(k\), and \(λ\) that must be satisfied in order for a BIBD\((v, k, λ)\) to exist.

Theorem \(\PageIndex{3}\)

A BIBD\((v, k, λ)\) cannot exist unless

\(λ \dfrac{v − 1}{k − 1} \text{ and } λ \dfrac{v(v − 1)}{k(k − 1)}\)

are integers.

Proof

By Equation \ref{17.1.4}, every point of the design must appear in

\(\dfrac{λ(v − 1)}{k −1} \)

blocks. Since a point can only appear in an integral number of blocks, the first result follows.

Similarly, By Equation \ref{17.1.5}, there must be

\(\dfrac{λv(v − 1)}{k(k − 1)} \)

blocks in the design. Since there can’t be a fractional number of blocks, the second result follows.

Although these conditions are necessary to the existence of a BIBD, there is no guarantee that a BIBD with specified parameters will exist, even if those parameters satisfy these conditions.

Example \(\PageIndex{3}\)

The parameters \(v = 15\), \(k = 5\), \(λ = 2\) satisfy the conditions of Theorem 17.1.3, but there is no BIBD\((15, 5, 2)\).

We will not prove that such a design does not exist as the proof would be tedious and unenlightening. We will verify that the parameters satisfy the necessary conditions.

We have

\(\dfrac{λ(v − 1)}{k −1} = \dfrac{2(14)}{4} = 7 \),

and

\(\dfrac{λv(v − 1)}{k(k − 1)} = 2 \cdot 15 \cdot \dfrac{14}{20} = 21 \).

Both of these are integers, so if a design were to exist, each point would appear in \(7\) blocks, and there would be \(21\) blocks. A computer search can verify that no such design exists.

Exercise \(\PageIndex{1}\)

1) Show that for any BIBD\((v, k, λ)\), the number of edges of \(λK_v\) is equal to the number of edges of \(K_k\) times the number of blocks of the design.

2) Suppose there is a BIBD\((16, 6, 3)\). How many blocks does it have? In how many of those blocks does each point appear?

3) Find an edge-colouring of \(K_5\) so that the edges of any colour form a \(K_2\). What are the parameters of the design to which this corresponds?

4) Here are the blocks of a BIBD with \(λ = 1\):

\(\begin{equation} \begin{split} &B_1 = \{1, 2, 3\} \;\;&B_2 = \{1, 4, 7\} \;\;&B_3 = \{1, 5, 9\} \;\;&B_4 = \{1, 6, 8\}\\ &B_5 = \{4, 5, 6\} \;\;&B_6 = \{2, 5, 8\} \;\;&B_7 = \{2, 6, 7\} \;\;&B_8 = \{2, 4, 9\}\\ &B_9 = \{7, 8, 9\} \;\;&B_{10} = \{3, 6, 9\} \;\;&B_{11} = \{3, 4, 8\} \;\;&B_{12} = \{3, 5, 7\}. \end{split} \end{equation}\)

(a) What are the values of \(v\), \(b\), \(k\), and \(r\) for this BIBD?

(b) How many of the blocks contain the element \(7\)?

(c) How many of the blocks contain both \(2\) and \(7\)?

(d) Which blocks contain the element \(5\)?

(e) Which blocks contain both \(5\) and \(8\)?

5) Assume \(\mathcal{B}\) is a BIBD with \(v = 16\), \(k = 4\), and \(r = 3\).

(a) What are the values of \(b\) and \(λ\)?

(b) Can you tell whether such a BIBD exists or not?

6) A prize draw allows you to enter by picking \(3\) numbers from \(\{1, . . . , 14\}\). You will win a prize if you choose two of the three numbers that they will draw. Show that it is possible to guarantee a win by having \(14\) entries in the draw. Explain whether or not a similar strategy would work if the numbers were chosen from \(\{1, . . . , 21\}\).

[Hint: Use the \((7, 7, 3, 3, 1)\) design.]