9 Designs 9 Designs 9.2 Fisher’s inequality for designs

9.1 Examples and basic properties

Let us see some examples. Trivial designs are single block consisting of all points or all $k$ -subsets of $\mathcal{P}$ . These are often not focus of study in designs.

As a first non-trivial example, a symmetric Steiner system $S(2,2,3)$ can be easily represented as triangle on $3$ points with the lines denoting the blocks.

Example 9.1 (Fano plane ).

This is simply the symmetric Steiner system $S(2,3,7)$ . More geometrically,

Alternatively, set $\mathcal{P}=\mathbb{Z}_{7}$ and ${\mathcal{B}}=\{(x,x+1,x+3):x\in\mathbb{Z}_{7}\}$ .

More generally, symmetric Steiner systems $S(2,q+1,q^{2}+q+1)$ are called as projective planes and we shall see more about them later. Why $k=q$ implies that $v=q^{2}+q+1$ follows from the below exercise which is via double counting of pairs of $t$ -sets and blocks containing them.

Exercise 9.2.

Show that in a $t-(v,k,\lambda)$ design $b=\lambda\binom{v}{t}/\binom{k}{t}.$

Example 9.3.

Let $\mathcal{P}=\mathbb{F}_{2}^{4}\setminus\{0\}$ and ${\mathcal{B}}=\{(x,y,z):x+y+z=0\}$ . Clearly $v=15,k=3$ . Take $x\neq y\in\mathcal{P}$ . Then clearly there exists a unique $z\in\mathcal{P}$ such that $x+y_{z}=0$ . Thus, any pair of points belongs to exactly one block i.e., this is a $S(2,3,15)$ .

A second Steiner system on $\mathcal{P}=\mathbb{F}_{2}^{4}$ is as follows : ${\mathcal{B}}=\{(w,x,y,z):w+x+y+z=0\}$ . This is a $S(3,4,16)$ . If we take blocks containing $0$ and delete $0$ , we get $S(2,3,15)$ , the previous Steiner system.

Exercise(A) 9.4.

Take the edges of $K_{6}$ as points. Let the blocks be sets of $3$ edges that either are the edges of a perfect matching or the edges of a triangle. Show that this is $S(2,3,15)$ . Is it isomorphic to the design in the above example ?

One of the first properties of designs is regularity as sets i.e., every point belongs to the same number of sets, say $r$ . $r$ is called as replication number.

Lemma 9.5.

Let ${\mathcal{B}}$ be a $(v,k,\lambda)$ design containing $b$ blocks. Then every point is contained in exactly $r$ blocks where $r$ satisfies

r(k-1)=\lambda(v-1)\,\,;\,\,bk=vr.

Proof.

We will prove by double counting. Let $p\in\mathcal{P}$ and suppose its replication number is $r_{p}$ . Let us count the cardinality of the set $\{(x,B):B\in{\mathcal{B}},p,x\in B,p\neq x\}$ .

For the $v-1$ points $x\neq p$ , there are exactly $\lambda$ blocks containing both $x, p$ . This gives the cardinality to be $\lambda(v-1).$

On the other hand, there are $r_{p}$ blocks $B$ containing $p$ and each of the blocks contains $k-1$ other points. So the cardinality $r_{p}(k-1).$ Thus we have $r_{p}(k-1)=\lambda(v-1)$ . This gives that $r_{p}$ is independent of $p$ . Now the second identity follows by double counting the set $\{(p,B):B\in{\mathcal{B}},p\in B\}$ . ∎

In other words, the above shows that a $(v,k,\lambda)$ design is also a $1-(v,k,r)$ design. More generally, we have the following.

Lemma 9.6.

Let ${\mathcal{B}}$ be a $t-(v,k,\lambda)$ design and let $0\leq i\leq t$ . Then it is also a $i-(v,k,\lambda_{i})$ design for

\lambda_{i}=\lambda\binom{v-i}{t-i}/\binom{k-i}{t-i}

Proof.

Fix an $i$ -set $I$ . Count the number of pairs $(T,B)$ such that $T$ is a $t$ -set containing $I$ and $T\subset B\in{\mathcal{B}}$ . Summing over $T$ gives that $\lambda\binom{v-i}{t-i}$ and summing over $B$ gives that $\lambda_{i}\binom{k-i}{t-i}$ . ∎

Exercise(A) 9.7.

Let $0\leq j\leq t$ and $J$ is a $j$ -subset of $\mathcal{P}$ . The number of blocks of an $t-(v,k,\lambda)$ design that contain none of the points of $J$ is

b_{j}=\lambda\frac{\binom{v-j}{k}}{\binom{v-t}{k-t}}.

Exercise(A) 9.8.

Let ${\mathcal{B}}$ be a $(v,k,\lambda)$ design with $b$ blocks and replication number $r$ . Prove that the complement ${\mathcal{B}}^{c}:=\{\mathcal{P}\setminus B:B\in{\mathcal{B}}\}$ is a design if $b-2r+\lambda>0$ . Determine the parameters.