18.2: t-Designs

In a BIBD, every pair appears together \(λ\) times. In the notation of Woolhouse’s problem, \(q = 2\). What about larger values of \(q\)? (We’ll still only consider the case where every \(q\)-set appears an equal number of times \(λ\), so the design must be balanced, but we will include the more general situation that \(λ ≥ 1\).)

Definition: \(t\)-\((v, k, λ)\) Design

A \(t\)-\((v, k, λ)\) design is a design on \(v\) points with blocks of cardinality \(k\), such that every \(t\)-subset of \(V\) appears in exactly \(λ\) blocks.

So far, all we have looked at have been \(2\)-designs.

Theorem \(\PageIndex{1}\)

In a \(t\)-\((v, k, λ)\) design,

\[\binom{k-1}{t-1} \text{ is a divisor of } λ\binom{v-1}{t-1} \text{ for every } 0 ≤ i ≤ t − 1. \]

Proof

We first consider the special case where \(i = 0\). Notice that in each of the \(b\) blocks, there are \(\binom{k}{t}\) subsets of cardinality \(t\) that appear in that block. So in the entire design, \(b\binom{k}{t}\) subsets of cardinality t appear.

There exist \(\binom{v}{t}\) subsets of cardinality \(t\) from the \(v\) points of \(V\), and each appears in \(λ\) blocks, so in the entire design, \(λ\binom{v}{t}\) subsets of cardinality \(t\) appear.

Thus, \(b\binom{k}{t} = λ\binom{v}{t}\).

Similarly, if we fix any set of \(i\) varieties, there are \(\binom{v-i}{t-i}\) subsets of cardinality \(t\) that include these \(i\) varieties. Each such subset appears in \(λ\) blocks. However, for each of the blocks that contains these \(i\) elements (the number of these will be our quotient), we can complete our \(i\)-set to a set of cardinality \(t\) that lies within this block, in \(\binom{k-i}{t-i}\) ways. Thus, we have counted any such block \(\binom{k-i}{t-i}\) times in the preceding count. So \(\binom{k-i}{t-i}\) must be a divisor of \(λ \binom{v−i}{t−i}\), as claimed.

Example \(\PageIndex{1}\)

Show that there is no \(5 − (16, 7, 1)\) design.

Solution

We check the necessary conditions given in Theorem 18.2.1. Using the condition when \(i = 0\), we see that \(b \binom{7}{5} = 1 \binom{16}{5}\), so \(21b = 4368\). Therefore \(b = 208\). This condition is satisfied.

When \(i = 1\) we have \(\binom{k-i}{t-i} = \binom{6}{4} = 15\), and \(λ \binom{v-i}{t-i} = \binom{15}{4} = 15·14·13·12 4·3·2 = 15 · 7 · 13\), which is divisible by \(15\). This condition is satisfied.

When \(i = 2\) we have \(\binom{k-i}{t-i} = \binom{5}{3} = 10\), and \(λ \binom{v-i}{t-i} = \binom{14}{3} = 14·13·12 3·2 = 14 · 13 · 2\), which is not divisible by \(10\) since it is not a multiple of \(5\). This condition fails. Thus, there is no \(5 −(16, 7, 1)\) design.

design. Suppose we have a \(3-(10, 4, 1)\) design. By Theorem 18.1.1, it

\(b \binom{4}{3} = 1 \binom{10}{3} \)

so \(4b = \dfrac{10 · 9 · 8}{6} = 120\). Thus, \(b = 30\). Also, since \(bk = vr\), we have \(30 · 4 = 10r\), so \(r = 12\)

Example \(\PageIndex{2}\)

Here is a \(3-(10, 4, 1)\) design.

\[\begin{equation} \begin{split} &\{1, 5, 6, 10\},\;\; &\{1, 2, 8, 9\}, \;\;&\{2, 3, 6, 7\},\;\; &\{3, 4, 9, 10\},\;\; &\{4, 5, 7, 8\}, \;\;&\{1, 3, 4, 7\}, \\ &\{2, 4, 5, 10\},\;\; &\{1, 3, 5, 8\},\;\; &\{1, 2, 4, 6\},\;\; &\{2, 3, 5, 9\},\;\; &\{4, 6, 8, 9\}, \;\;&\{1, 7, 9, 10\}, \\ &\{3, 6, 8, 9\},\;\; &\{5, 6, 7, 9\}, \;\;&\{2, 7, 8, 10\},\;\; &\{1, 2, 3, 10\},\;\; &\{1, 2, 5, 7\}, \;\;&\{1, 4, 5, 9\}, \\ &\{1, 3, 6, 9\}, \;\;&\{1, 6, 7, 8\},\;\; &\{1, 4, 8, 10\},\;\; &\{2, 3, 4, 8\},\;\; &\{2, 4, 7, 9\},\;\; &\{2, 5, 6, 8\}, \\ &\{2, 6, 9, 10\},\;\; &\{3, 4, 5, 6\},\;\; &\{3, 5, 7, 10\}, \;\;&\{3, 7, 8, 9\},\;\; &\{4, 6, 7, 10\}, &\;\;\{5, 8, 9, 10\} \end{split} \end{equation}\]

Notice: For \(t ≥ 3\), a \(t\)-design is also a \((t − 1)\)-design. If every \(t\)-set appears in exactly \(λ\) blocks, then any \((t − 1)\)-set must appear in exactly

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

blocks. This is because if we fix a \((t − 1)\)-set, it can be made into a \(t\)-set by adding any one of the \(v − t + 1\) other elements of \(V\). Each of these \(t\)-sets appears in \(λ\) of the blocks. However, some of these blocks are the same; in fact, we have counted each block containing this \((t−1)\)-set once for every other element of the block (since every other element of the block forms a \(t\)-set when put together with the \((t − 1)\)-set). So every block that contains this \((t − 1)\)-set has been counted \(k −(t−1)\) times. The result follows. (From the above formula we can see that \(k −t+ 1\) is a divisor of \(λ(v − t + 1)\); this is exactly the condition that Theorem 18.2.1 gives when we take \(i = t − 1.\))

Therefore, since

\(\dfrac{1(10 − 3 + 1)}{(4 − 3 + 1)} = 4\),

the \(3 − (10, 4, 1)\) design that we gave above, is also a \(2 − (10, 4, 4)\) design. In more generality, a \(t − (v, k, λ)\) design with \(t > 2\) is also a \((t − 1) − \left( \dfrac{v, k, λ(v − t + 1)}{(k − t + 1)} \right)\) design.

Steiner’s name is also used in this more general context, and without the constraint on the block

Definition: Steiner System

A Steiner system is a \(t\)-design with \(λ = 1\).

The \(3-(10, 4, 1)\) design above is a Steiner system.

Our ability to construct Steiner systems when \(k > 3\), or when \(t > 2\), except in trivial cases, is almost nonexistence. In fact, there are no known constructed Steiner systems with \(t > 5\), with the exception that taking every possible \(t\)-subset of a \(v\)-set is always a (trivial) \(t − (v, t, 1)\) design.

Despite this, in \(2014\) a remarkable theorem was proved by Peter Keevash, along similar lines to Wilson’s Theorem, but applying to this more general context.

The necessary conditions given in Theorem 18.1.1 are not sufficient to guarantee the existence of a BIBD with a particular set of parameters. However, Keevash’s Theorem tells us that if we fix \(k\) and \(t\), there are only finitely many values for \(v\) that satisfy the necessary conditions but for which no \(t − (v, k, 1)\) design exists. His proof was probabilistic, so does not produce constructions for any designs. Here is a formal statement of Keevash’s Theorem.

Theorem \(\PageIndex{2}\): Keevash's Theorem

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

• \(v ∈ \mathbb{Z}\); and
• for every \(0 ≤ i ≤ t − 1\),

\[\binom{k-1}{t-1} \text{ is a divisor of } λ\binom{v-1}{t-1} \]

a \(t − (v, k, 1)\) design exists.

Proof

We will not give a proof of this theorem.

Exercise \(\PageIndex{1}\)

1) Substituting \(t = 2\) into the equations of Theorem 18.1.1 doesn’t immediately look like either of the equations in Theorem 17.1.1. Use the equations of Theorem 17.1.1 to deduce that

\(\binom{k}{2} \text{ is a divisor of } λ\binom{v}{2} \)

2) If \(v = 15\) and \(λ = 1\), what are all possible values of \(k\) and \(t ≥ 2\) for which \(t\)-designs might exist? Do not include any trivial \(t−(v, t, 1)\) design, so you may assume \(v > k > t\).

3) Is it possible for a \(3-(16, 6, 1)\) design to exist? If so, how many blocks will it have? What will the value of \(r\) be?

4) Let \(B\) be the \((7, 3, 1)\)-design. Define a new design \(D\) as follows, on the varieties \(\{1, . . . , 8\}\). It has \(14\) blocks, of two types:

(I) the blocks of \(B\) but with variety \(8\) added to each; and

(II) the blocks of the complementary design to \(B\).

Prove that this is a Steiner system with \(t = 3\), \(k = 4\), and \(v = 8\). Use the structure of \(B\) and its complement to show that \(λ = 1\); do not check all \(\binom{8}{3}\) possible \(3\)-subsets of \(\{1, . . . , 8\}\).

5) Define a design as follows. Label the edges of the complete graph \(K_6\); these will be the varieties of the design. The blocks are of two types:

(I) any set of three edges from \(K_6\) that can be properly coloured with the same colour; and

(II) any set of three edges that form a triangle in \(K_6\).

Determine the parameters of this \(t\)-design (including the highest value of \(t\) for which this is a \(t\)-design, and justifying each value you determine), and show that this is a Steiner system.

6) Might a \(3 − (20, 5, 8)\) design exist according to the necessary conditions we have determined (Theorem 18.1.1)? State the formulas that must be satisfied and show your work.