Combinatorics

17.1.11.1 Numerically, this property is easy to verify from the proof of Theorem 17.1.9, which tells us that if \(\displaystyle b\) is the number of blocks, then \(\displaystyle b=\frac{\lambda v(v-1)}{k(k-1)}\text{,}\) so (dividing both sides by \(\displaystyle 2\) and multiplying through by \(\displaystyle k(k-1)\)) we have \(\displaystyle b \binom{k}{2} = \lambda \binom{v}{2}\text{.}\)

The correspondence is due to the colouring explained in Theorem 17.1.8.

17.1.11.2 We are given that \(\displaystyle v = 16\text{,}\) \(\displaystyle k = 6\text{,}\) and \(\displaystyle \lambda = 3\text{.}\)

From the formula \(\displaystyle r(k-1) = \lambda(v-1)\text{,}\) we see that

which means that each point is in \(\displaystyle 9\) blocks.

Now, from the formula \(\displaystyle bk = vr\text{,}\) we haveThis means that the design has \(\displaystyle 24\) blocks.

17.2.8.1 Proof. Clearly the complement of a design will still have \(\displaystyle v\) varieties. (It will also have \(\displaystyle b\) blocks, since each of its blocks comes from one block of the original design.)

From a block \(\displaystyle B\) of size \(\displaystyle k\text{,}\) the corresponding block of the complementary design will have the \(\displaystyle v-k\) elements of \(\displaystyle V\setminus B\text{.}\)

We need to count how many times any given pair of varieties appear together in a block of the complementary design. Two varieties appear together in a block of the complementary design if and only if neither of them was in the corresponding block of the original design. Each of the two varieties appeared in \(\displaystyle r\) blocks of the original design, and they appear together in \(\displaystyle \lambda\) blocks of the original design. We can now use inclusion-exclusion to count the number of blocks in which at least one of the two varieties appears: \(\displaystyle r+r-\lambda=2r-\lambda\text{.}\) Thus, the number of blocks in which neither of them appears is \(\displaystyle b-(2r-\lambda)=b-2r+\lambda\text{,}\) as claimed. Since this count in no way depended on the choice of our two varieties, the complement is indeed a design, as every pair of varieties appear together in some block \(\displaystyle b-2r+\lambda\) times. ◾

17.2.8.3 The set \(\displaystyle \{1,3,7\}\) gives the differences \(\displaystyle \pm 2\text{,}\) \(\displaystyle \pm 4\text{,}\) and \(\displaystyle \pm6\text{,}\) while the set \(\displaystyle \{1,6,13\}\) gives the differences \(\displaystyle \pm 5\text{,}\) \(\displaystyle \pm 7\text{,}\) and \(\displaystyle \pm 12\text{.}\) So we need to find two sets that contain the differences \(\displaystyle \pm 1\text{,}\) \(\displaystyle \pm 3\text{,}\) \(\displaystyle \pm 8\text{,}\) \(\displaystyle \pm 9\text{,}\) \(\displaystyle \pm 10\text{,}\) and \(\displaystyle \pm 11\text{.}\) The sets \(\displaystyle \{1,2,11\}\) and \(\displaystyle \{1,4,12\}\) work.

17.3.2.1 Many examples are possible (but they may be hard to find). For example, letThenandare integers, so the conditions in Theorem 17.1.9 are satisfied.

From the formula \(\displaystyle r(k-1) = \lambda(v-1)\text{,}\) we see that

Then, from the formula \(\displaystyle bk = vr\text{,}\) we have

Therefore \(\displaystyle b = 8 \lt 16 = v\text{,}\) so Fisher's Inequality is not satisfied.

Since Fisher's Inequality is not satisfied, there is no BIBD with these parameters.

17.3.2.2 It is shown just before the proof of Fisher's Inequality that Fisher's Inequality is equivalent to \(\displaystyle \lambda(v-1) \ge k(k-1)\text{.}\) Since \(\displaystyle \lambda = 1\) and \(\displaystyle k = 20\text{,}\) this meansso \(\displaystyle v \ge 380 + 1 = 381\text{.}\) Therefore, \(\displaystyle v\) must be at least \(\displaystyle 381\) to satisfy Fisher's Inequality.

Sinceandare integers, the conditions in Theorem 17.1.9 are also satisfied. So \(\displaystyle 381\) is the smallest value for \(\displaystyle v\) that satisfies all three conditions.