224 14. Finite Geometries, Codes,Latin Squares,and Other Pretty Creatures
ClubsCitizensmember of...FIGURE 14.9. Representing club membership by a graph14.9 we have drawn only one edge of the graph). We know the following
properties of our graph: from every point below, exactlyredges go up, and
from every upper point exactlykedges go down. Below we havevpoints,
abovewehavebpoints. If we choosenpoints from the lower set (obviously,
n≤v), then we know that from thesenpointsnr edges leave. Let us
denote bymthe number of other endpoints of thesenredges.
We claim thatn≤m. Since every upper point has degreek, altogether
this makesmkedges. Thenredges mentioned above are among thesemk
edges, and hence
nr≤mk. (14.4)
On the other hand,bk=vrby (14.1). Byb≥vwe getk≤r, and so
mk≤mr. (14.5)From (14.4) and (14.5) we get
nr≤mr,and thereforen≤m, as claimed.
So anynlower points are connected to at leastnupper points. We invoke
the Marriage Theorem, more precisely, its version stated in Exercise 10.3.2:
We get that there exists a matching of the lower set into the upper set, i.e.,
there existvindependent edges that connect every lower point to a different
point above. This matching tells every citizen which badge to wear.
14.4 Steiner Systems.........................
We have seen that block designs withk≤2 are trivial; we take a closer
look at the next case,k = 3. We also take the smallest possible value
forλ, namelyλ= 1. Block designs withk= 3 andλ= 1 are called
Steiner systems(named after Jakob Steiner, a Swiss mathematician in the
nineteenth century). The Fano plane and the Tictactoe plane are Steiner
systems, but the Cube space is not.