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 𝒫. 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 𝒫=7 and ={(x,x+1,x+3):x7}.

More generally, symmetric Steiner systems S(2,q+1,q2+q+1) are called as projective planes and we shall see more about them later. Why k=q implies that v=q2+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,λ) design b=λ(vt)/(kt).

Example 9.3.

Let 𝒫=𝔽24{0} and ={(x,y,z):x+y+z=0}. Clearly v=15,k=3. Take xy𝒫. Then clearly there exists a unique z𝒫 such that x+yz=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 𝒫=𝔽24 is as follows : ={(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 K6 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 be a (v,k,λ) design containing b blocks. Then every point is contained in exactly r blocks where r satisfies

r(k1)=λ(v1);bk=vr.
Proof.

We will prove by double counting. Let p𝒫 and suppose its replication number is rp. Let us count the cardinality of the set {(x,B):B,p,xB,px}.

For the v1 points xp, there are exactly λ blocks containing both x,p. This gives the cardinality to be λ(v1).

On the other hand, there are rp blocks B containing p and each of the blocks contains k1 other points. So the cardinality rp(k1). Thus we have rp(k1)=λ(v1). This gives that rp is independent of p. Now the second identity follows by double counting the set {(p,B):B,pB}. ∎

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

Lemma 9.6.

Let be a t(v,k,λ) design and let 0it. Then it is also a i(v,k,λi) design for

λi=λ(viti)/(kiti)
Proof.

Fix an i-set I. Count the number of pairs (T,B) such that T is a t-set containing I and TB. Summing over T gives that λ(viti) and summing over B gives that λi(kiti). ∎

Exercise(A) 9.7.

Let 0jt and J is a j-subset of 𝒫. The number of blocks of an t(v,k,λ) design that contain none of the points of J is

bj=λ(vjk)(vtkt).
Exercise(A) 9.8.

Let be a (v,k,λ) design with b blocks and replication number r. Prove that the complement c:={𝒫B:B} is a design if b2r+λ>0. Determine the parameters.