It is very exciting to look at a few applications of the geometries that we have been studying. Many of the problems are combinatorial in nature, and while seeming very complicated, actually have simple (and beautiful) solutions when geometry is used. One famous problem is Kirkman's School Girl Problem.

Fifteen schoolgirls walk each day in five groups of three. Arrange the girls' walk for a week so that in that time, each pair of girls walks together in a group just once.

Ok, now, let's recall from Problem 16 the axioms for a design.

Notice that in axioms 4 and 5, we refer to lines containing our points. Since one can not always draw lines in a given geometry as straight lines (but must instead use circles, triangles, etc) we some autors prefer to replace the word line with the word block. In the examples of designs that we will look at, we will define our blocks to be triangles.

A special type of design is called a Steiner Triple System (STS). An STS is a 2 -(v,3,1) design. We call v the order of the STS. An STS of order v will exist if and only if v = 1 or 3 mod 6. We can identify the v-many points of a given STS with the vertices of a complete graph and every block of our STS will correspond to a triangle with edges of the graph.

Let's look at an example to help understand this concept better. The Fano Plane is the smallest example of a nontrivial STS. It's order is 7. However, every figure of the Fano Plane that we have seen so far contains 7 points and 7 lines. In the case of the STS, the Fano Plane will contain 7 triangles rather than 7 lines, and the triangles correspond to edges of the complete graph on 7 points. Often when looking at STSs, it is simpler to look at a generator-only graph, meaning that a given graph is rotated a given number of times to generate the entire graph. Because STSs stem from complete graphs, they quickly become very complicated. Here is one generator-only picture of the Fano Plane.

Below is the completed STS of the Fano plane. We rotate our generator until we have created the complete graph on 7 vertices. Each block corresponds to a different color in the above STS. (To stop the animation, drag the mouse onto the black rectangle).

Note that like the Fano plane, each triangle is incident with 3 points. In addition, the color-coding above makes it easy to see that each point is incident with 3 triangles. You can also check that each triangle meets every other triangle at a given point and that every point is joined to every other point via a triangle. Using these triangles as "lines" it is easy to see that this STS satisfies the axioms of a projective plane, and so must be the Fano Plane, the unique projetive plane of order 2.

Now let's try to solve Kirkman's problem. We will look at the STS on 15 points. There are 80 different STSs of order 15! Let's look at one example.

This is the generator for an STS of order 15. We let the points correspond to each one of the girls proposed in the original problem. Note that in the generator, each girl is paired with two others. If we rotate the STS 7 times (the number of days in a week!), the images of these rotations correspond to a solution to the problem. Note that each point will be joined to another point via a triangle. This is not the unique solution, however!

Here is a completion of the generator-only figure. The STS on the right assigns a different color to each of the 7 images:

References: Polster