Skip to main content
Mathematics LibreTexts

17.2: Constructing Designs and Existence of Designs

  • Page ID
    60162
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    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, λ)\). For each block of the design, create \(t\) copies of that block. The result will be a BIBD\((v, k, tλ)\).

    Method \(2\): Taking the complement

    This method also requires starting with a design. Start with \((V, B)\), a BIBD\((v, k, λ)\).

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

    \((V, \{B^c | B ∈ B\})\)

    is a design.

    Definition: Complementary Design

    We call the design constructed by this method, the complementary design or complement of the design we started with.

    Proposition \(\PageIndex{1}\)

    The complement of a BIBD\((v, k, λ)\) is a BIBD\((v, v − k, b − 2r + λ)\).

    Proof

    The proof of this proposition is left to the reader, as Exercise 17.2.1(1).

    Example \(\PageIndex{1}\)

    The complement of the design given in Example 17.2.2, is the following:

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

    Its parameters are \(b = 20\), \(v = 16\), \(r = 15\), \(k = 12\), \(λ = 11\).

    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 the most basic version. This most basic version unfortunately only works when \(v\) is odd.

    Definition: Difference Collection and Difference Set

    Fix an odd integer \(n\). A collection of sets \(D_1, . . . , D_m ⊆ \{1, . . . , n\}\) is a difference collection for \(n\), if taking the differences \(j − i\) for every pair \(i \neq j\) with \(i\), \(j ∈ D_k\) for each set \(D_k\), attains each of the values \(±1, . . . , ±\dfrac{(n − 1)}{2}\), exactly once, when computations are performed modulo \(n\). If \(m = 1\) then \(D_1\) is called a difference set.

    Example \(\PageIndex{2}\)

    The collection \(\{1, 2, 5\}\), \(\{1, 3, 10\}\), \(\{1, 7, 15\}\) is a difference collection for \(n = 19\). The differences we attain appear in the following table.

    Difference Set \(i\) \(j\) \(j − i, i − j\)
    \(D_1\) \(1\) \(2\) \(±1\)
    \(D_1\) \(1\) \(5\) \(±4\)
    \(D_1\) \(2\) \(5\) \(±3\)
    \(D_2\) \(1\) \(3\) \(±2\)
    \(D_2\) \(1\) \(10\) \(±9\)
    \(D_2\) \(3\) \(10\) \(±7\)
    \(D_3\) \(1\) \(7\) \(±6\)
    \(D_3\) \(1\) \(15\) \(±14 ≡ ±5 (\text{mod } 19)\)
    \(D_3\) \(7\) \(15\) \(±8\)

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

    \(\{d + \ell (\text{mod } v) | d ∈ D_i\}\),

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

    \(\{D_i + \ell | 1 ≤ i ≤ m, 0 ≤ \ell ≤ v − 1\}\)

    form a BIBD\((v, |D_1|, 1)\).

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

    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 \(λ = 1\). 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\). 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 \(\dfrac{(v − 1)}{2}\), \(K_v\) has \(v\) edges of that length. (This is where the trouble arises if \(v\) is even: there are only \(\dfrac{v}{2}\) edges of length \(\dfrac{v}{2}\).) 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\).

    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\), since \(v = 19\) and \(k = 3\). The edge lengths in \(K_{19}\) are \(\{1, . . . , 9\}\). We will show three \(K_3\)s, such that every edge length from \(\{1, . . . , 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. This textbook is printed in black-and-white, so, instead of drawing actual colours on the edges, we will draw solid edges for blue, dotted edges for red, and dashed edges for green.

    clipboard_e5276a8061fb9b05a08b3193378a9ad15.png

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

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

    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.3 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. It tells us that if we fix \(k\), 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, λ)\) for any \(λ\). Here is a formal statement of Wilson’s Theorem.

    Theorem \(\PageIndex{1}\): Wilson's Theorem

    Given \(k\), there is an integer \(v(k)\) such that for every \(v > v(k)\) that satisfies the three conditions:

    • \(v ∈ \mathbb{Z}\);
    • \(\dfrac{v(v − 1)}{[k(k − 1)]} ∈ \mathbb{Z}\); and
    • \(\dfrac{(v − 1)}{(k − 1)} ∈ \mathbb{Z}\),

    a BIBD\((v, k, 1)\) exists.

    Proof

    We will not give a proof of this theorem.

    Exercise \(\PageIndex{1}\)

    1) Prove that the complement of a BIBD is indeed a design, and that it has the parameters we claimed in Proposition 17.2.1.

    [Hint: Use inclusion-exclusion to determine how many blocks of the original design contain neither point from an arbitrary pair.]

    2) Find the complement of the BIBD\((8, 4, 3)\) given by \(V = \{1, 2, 3, 4, 5, 6, 7, 8\}\) and

    \[\mathcal{B}=\left\{ \begin{array}{ll} \{1, 2, 3, 4\}, \{5, 6, 7, 8\}, \{1, 2, 5, 6\}, \{1, 2, 7, 8\}, \{3, 4, 5, 6\}, \{3, 4, 7, 8\}, \{2, 4, 6, 8\},\\ \{1, 3, 5, 7\}, \{1, 3, 6, 8\}, \{2, 4, 5, 7\}, \{1, 4, 5, 8\}, \{1, 4, 6, 7\}, \{2, 3, 5, 8\}, \{2, 3, 6, 7\}\end{array}\right\}.\]

    3) By adding two more sets to the sets \(\{1, 3, 7\}\) and \(\{1, 6, 13\}\), you can create a difference collection for \(25\) in which each of the sets has \(3\) elements, and thus a cyclic BIBD\((25, 3, 1)\). Find two sets to add.

    4) Use a difference set to construct a cyclic \((11, 11, 5, 5, 2)\) design.

    5) Show that the collection \(\mathcal{C} = \left\{ \{0, 1, 3\}, \{0, 4, 5\}, \{0, 4, 7\}, \{0, 5, 7\} \right\} \) is a difference collection for \(13\). Construct the design and give its parameters.

    6) Determine whether the given set \(D\) is a difference set for the given value of \(n\). If it is a difference set, find the parameters of the resulting cyclic BIBD.

    (a) \(D = \{1, 2, 4, 10\}\) for \(n = 13\).

    (b) \(D = \{2, 4, 5, 6, 10\}\) for \(n = 21\).

    7) Prove that in any cyclic design, there exists an integer \(c\) such that \(b = cv\), \(ck(k − 1) = λ(v − 1)\), and \(r = ck\). What is the significance of \(c\) in terms of the design?

    8) Explain why a BIBD with \(v = 6\), \(b = 10\), \(k = 3\), \(r = 5\), and \(λ = 2\) cannot be cyclic.

    9) Does the condition you proved in Problem \(7\) show that a BIBD with \(v = 61\), \(b = 305\), \(k = 4\), \(r = 20\), and \(λ = 1\) cannot be cyclic?


    This page titled 17.2: Constructing Designs and Existence of Designs is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Joy Morris.

    • Was this article helpful?