Steiner Triple Systems

Another often-studied class of BIBDs is the class with k = 3 and = 1. Definition 7 A (b, v, r, 3, 1)-design is called a Steiner triple system.

While these are named for Jacob Steiner, they first arose in a problem called Kirkman's Schoolgirl Problem (1847).

Example 7 Suppose that 15 girls go for a walk in groups of three. They perform this each of the seven days of the week. Can they choose their walking partners so that each girl walks with each other girl exactly once in a week?

Solution: This amounts to finding a Steiner triple system with v = 15 (girls), b = 35 (there are five groups of girls each day for seven days), and r = 7 (each girl walks on seven days). Further, the 35 blocks must be divided into seven groups of five so that each girl appears exactly once in each group.

Number the girls 0,1,2,...,14. Let the first group be

{14, 1, 2}, {3, 5, 9}, {11, 4, 0}, {7, 6, 12}, {13, 8, 10}.

Then let group i (1 i 6) be obtained as follows:

a) 14 remains in the same place,

b) if 0 k 13, k is replaced by (k + 2i) mod 14.

184 Applications of Discrete Mathematics

It is left as an exercise to show that the seven groups obtained actually give 35 different blocks of the type desired.

Steiner conjectured in 1853 that Steiner triple systems exist exactly when v3andv1or3(mod6). Thishasproventobethecase. Inthecase wherev=6n+3,wehaveb=(2n+1)(3n+1). (SeeExercise9.)

If the b triples can be partitioned into 3n+1 components with each variety appearing exactly once in each component, the system is called a Kirkman triple system. Notice that the solution to the Kirkman schoolgirl problem has n = 2. For more results about Steiner triple systems, see [3] or [5].

12. There is a unique Steiner triple system with v = 7.

a) What are its parameters as a BIBD?

b) Construct it.

c) Use it to construct a finite projective plane. What order is it?