7 - Resolutions and partition systems
Published online by Cambridge University Press: 16 March 2010
Summary
…fiddle with pentagrams
Or barbituric acids, or dissect
The recurrent image into pre-conscious terrors …
(T. S. Eliot: The Dry Salvages)In this chapter, the concept of ‘parallelism’ is generalized in two ways. First, observing that (in the notation of Steiner systems) a parallelism is a resolution or partition of S(t, t, n) into systems S(l, t, n), I discuss other resolution problems, commencing with Kirkman's schoolgirl problem. Secondly, a more direct generalization is given, and a little of its theory is developed.
Kirkman originally suggested a problem which we may separate into three parts as follows.
(i) How may 15 schoolgirls go for a walk in 5 rows of 3? The answer is simply a partition S(1, 3, 15). (It has been suggested that the S stands for ‘schoolgirls’!)
(ii) How may the schoolgirls walk every day for a week, the walk on each day conforming with condition (i), so that any two girls walk together just once? The answer is a resolution (which we shall write S(2, 3, 15) ← S(1, 3, 15)) of a Steiner triple system on 15 points. (7 is the right number, since S(2, 3, 15) has 5. 7 blocks.) A Steiner triple system (on v points) possessing such a resolution is called a Kirkman system. The problem was solved by Kirkman [22], [23] for v = 15; over 120 years later, Ray-Chaudhuri and Wilson [25] proved that a Kirkman system S(2, 3, v) exists if and only if v = 3 (mod 6).
- Type
- Chapter
- Information
- Parallelisms of Complete Designs , pp. 129 - 137Publisher: Cambridge University PressPrint publication year: 1976