Kirkman’s schoolgirls and their friends

Often it happens that, when I think about a hard problem, I am absolutely convinced that I know what the answer will be, but I merely lack a proof. In this post I want to discuss a problem which I think may be hard, but where I have no idea whether the assertion is true or false.

The problem is not new, but it has some connection to Kirkman’s schoolgirls. I have been reminded of it by two recent events. First was Nigel White’s comment to my post on the Royal Institution, where he recounted having proposed and solved for himself Kirkman’s original problem. Then I found myself marking an undergraduate project which gave a self-contained account of the proof of the general case.

Kirkman’s schoolgirls

In 1850, the Reverend Thomas Penyngton Kirkman, vicar of Croft, posed the following problem in The Lady’s and Gentleman’s Diary:

Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast.

In seven days, each girl walks with fourteen others, none more than once (according to the conditions of the problem); thus each pair of girls walks together exactly once.

Kirkman solved the problem himself (apparently none of the readers of the journal did so). However, it can be generalised to the case where the number of schoolgirls is 6m+3 and the number of days is 3m+1, for any natural number m. In this form the problem attracted a lot of attention, but was not solved until 1969 when Dijen Ray-Chaudhuri and Richard Wilson showed that the arrangement is possible for any value of m.

For a simple illustration, here is the unique scheme for nine schoolgirls to walk for four days:

  • Day 1: ABC, DEF, GHI
  • Day 2: ADG, BEH, CFI
  • Day 3: AEI, BFG, CDH
  • Day 4: AFH, BDI, CEG

If you write the letters A, …, I in a 3×3 matrix, you will recognise the rows, the columns, and the positive and negative terms in the formula for the determinant of the matrix.

Though Kirkman is chiefly remembered now for his interest in schoolgirls, he was a significant mathematician, working also on group theory, theory of knots, polyhedra, and quaternions, and was a Fellow of the Royal Society.

Sylvester extended Kirkman’s problem by asking whether it is possible for the 15 schoolgirls to walk every day for a term of 13 weeks, in such a way that

  • in each week, every two girls walk together exactly once; and
  • in the whole term, every three girls walk together exactly once.

This is more difficult, and it was not until 1974 that Ralph Denniston provided a solution.

Steiner systems

Let t, k and v be integers with 1≤tkv. A Steiner system S(t,k,v) consists of a set of v points with a collection of k-element subsets called blocks, such that any t points are contained in just one block.

The example above with the nine schoolgirls is thus a S(2,3,9).

The cases where one or more of the inequalities is satisfied with equality are more or less straightforward. If t=1, we have simply a partition of the set of points into subsets of size k; if k=t, the blocks are all the subsets of size k; and if v=k, then there is a single block, containing all the points. It will become clear later why I do not simply exclude these trivial cases.

This simple and elegant definition is not in fact due to Steiner. It was proposed by Kirkman in 1847, with the problem of deciding for which numbers t,k,v they exist. He soon realised that this was too hard, but he solved completely the case t=2, k=3 (these systems are now called Steiner triple systems), by showing that such a system exists if and only if v is congruent to 1 or 3 (mod 6). Six years later, Steiner posed a problem of which the first case was equivalent to the existence of “Steiner triple systems”, unaware that Kirkman had already solved this; Steiner’s other cases are slightly different from Kirkman’s. So the name is a double misnomer. But we cannot change the terminology to “Kirkman triple system” now, since this means a solution to Kirkman’s schoolgirls problem.

Given t and k, it is not hard to write down some congruences on v which are necessary for the existence of a Steiner system with these parameters. In the case k=2, Richard Wilson’s existence theory (which I discussed in an earlier post) shows that these necessary conditions are sufficient for all but finitely many values. But for larger values of t, very little is known. For example, no single non-trivial example of a Steiner system with t>5 has ever been discovered!

Partitions

A Kirkman triple system (a solution to the schoolgirls problem) for v schoolgirls is a Steiner triple system with extra structure. Each day, the set of girls is partitioned into v/3 triples; these form a Steiner system S(1,3,v). So a Kirkman triple system is a Steiner system S(2,3,v) whose blocks are partitioned into Steiner systems S(1,3,v).

There are some interesting and difficult questions about such partitions, mostly unanswered. One of the few results we have has its roots in the 19th century as well. Arthur Cayley knew that there is a unique S(2,3,7) (this is the so-called Fano plane); he also knew that it was not possible to partition S(3,3,7) (the set of all 3-element subsets of 7 points) into copies of S(2,3,7). (In fact, Cayley showed that you cannot find more than two disjoint copies of the Fano plane; a partition would require five copies.) However, Luc Teirlinck has shown that, if v is an admissible order of Steiner triple systems (that is, congruent to 1 or 3 (mod 6)), and v>7, then it is possible to partition S(3,3,v) (the set of all triples) into Steiner triple systems S(2,3,v).

In general, a set of Steiner systems which partitions the set of all k-element subsets of points is called a large set.

Sylvester’s problem asks for a bit more, namely a large set of Kirkman triple systems (a partition of all the triples into Kirkman systems; so we have an extra level, since each Kirkman system itself has a partition). The general question is not yet solved.

Projective planes

Now I look at the other side of the problem. It is not difficult to show that, if a Steiner system S(2,k,v) has v>k (that is, if it is not the trivial case of a single block containing all the points), then in fact vk2k+1. To see this, let B be a block, and p a point not in v. Then the blocks “joining” p to the k points of B are all distinct, and each contains k−1 points different from p.

If equality holds, the system is called a finite projective plane. Usually we write k=q+1, and call q the order of the plane; we have v=q2+q+1.

Our ignorance about the existence of projective planes is very deep. The facts are as follows:

  • If q is a prime power, there is a projective plane of order q, constructed using linear algebra over the Galois field with q elements.
  • If q is congruent to 1 or 2 (mod 4) and q is not the sum of two squares, then there is no projective plane of order q. This is the celebrated Bruck–Ryser Theorem.
  • The smallest value not settled by these two results is q=10. There is no projective plane of order 10. This is the result of a huge computation by Clement Lam and co-authors. I understand that this computation has now been independently checked, but I don’t know the details.

So it might be that projective planes exist only for prime power orders, or it might be that they exist for infinitely many other values; we have no idea!

Hyperovals

The blocks of a projective plane are usually called lines, and we speak of “collinearity”, “concurrence”, etc. with their usual geometric meaning.

A hyperoval in a projective plane of order q is a set of q+2 points, no three of which are collinear. It is easy to see that this is the maximum size of a set of points with no three collinear. For each point of the plane lies on q+1 lines; and in a set with this property, the lines joining one point to all the others must all be distinct. This argument also shows that if a line contains one point of a hyperoval, it must also contain a second point.

It is also easy to see that a projective plane containing a hyperoval must have even order. For take a point p outside the hyperoval H. Then each line joining p to a point of H must contain exactly two points of H; so there are |H|/2=(q/2)+1 such lines.

Now let H be a hyperoval. Each line meeting H does so in two points, and is the unique line containing these two points. So the lines meeting H can be identified with the pairs of points of H. For each point p outside H, the lines through p meeting H cut it up into parts of size 2. Let us call a partition of H into parts of size 2 a factor. Then the set F of factors defined by such points has the property that, given any four points a,b,c,d of H, there is a unique factor in F having {a,b} and {c,d} as parts.

Let us call a set of factors with this property a factor 2-cover.

Now, knowing the hyperoval H and the factor 2-cover F, we can recover a little more than half of the projective plane. The points of the plane are the points of H and the factors in F; the lines meeting H are the pairs of points of H; and there are obvious rules for deciding when a point is incident with a line.

To construct the rest of the plane, we have to identify the lines disjoint from H. Any such line consists of a set of factors forming a factor 1-cover (sometimes called a factorisation); that is, each pair is a part in just one of them. The collection of factor 1-covers must have the property that any two disjoint factors lie together in just one factor 1-cover.

Let us stop and remark that even constructing the factor 2-cover gives us something very interesting. We have more than half of the projective plane; but, also, the pairs of points of H and the factors in the factor 2-cover form an example of a structure called a partial geometry.

So what we would like to do is to construct a factor 2-cover which doesn’t come from a known projective plane. Then we have a new partial geometry, and maybe with a bit more work, a new projective plane!

A construction

So here is the idea for a construction.

First, a particular kind of Steiner system, an affine geometry. The points of the system are the vectors in a d-dimensional vector space over the binary field {0,1}. The blocks are all the sets of {a,b,c,d} with a+b+c+d=0. It is easy to see that any three of the four vectors a,b,c,d determine the fourth uniquely, and if the first three are all distinct then the fourth is different from all of them. So we have constructed a Steiner system S(3,4,2d).

This system also provides us with a factor 1-cover, in which the parts of the factor containing {a,b} are all the pairs {c,d} for which a+b=c+d: that is, the pair {a,b} together with all pairs {c,d} for which {a,b,c,d} is a block. (Geometrically, each factor is a parallel class.)

Now suppose that we have a partition of S(4,4,2d) (the set of all 4-element sets) into Steiner systems S(3,4,2d), each isomorphic to the affine geometry. Consider all the factors in the factor 1-covers corresponding to these geometries. I claim that these form a factor 2-cover. For given {a,b,c,d}, there is a unique affine geometry in which this set is a block, and then a unique factor in this geometry containing {a,b} and {c,d}.

So we have a partial geometry, and perhaps (we might hope) a projective plane! (In fact, there cannot be a projective plane from this construction. For its order would have the form 2d−2, which is congruent to 2 (mod 4) but not the sum of two squares, so it is ruled out by the Bruck–Ryser Theorem.)

So finally the problem I want to pose is:

Is it ever possible to partition the 4-subsets of a set of 2d points into affine geometries?

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems and tagged , , , , , . Bookmark the permalink.

5 Responses to Kirkman’s schoolgirls and their friends

  1. Gordon Royle says:

    I don’t know the answer to your question, but is it possible that one factor 2-cover could give rise to different projective planes, by choosing a different factorisation to in order to “complete the plane”.

    It would be nice to be able to make some new projective planes – the number of known planes of order 16 has been stuck for quite a while, but I am not sure whether anyone believes it is complete.

  2. Randy Hudson says:

    I found this blog while searching for a construction of a solution to an analog for the (16,4) case of Sylvester’s extension to Kirkman’s schoolgirls. That is, with 16 girls walking in groups of 4, they cam form different groups on each of the 5 weekdays. Can they do that in each of 7 weeks, such that no three of them are contained within such a group of 4 more than once?

    I can find an arrangement of 140 S(3,4,16) into 35 collections of 4, so each set of 4 is a S(1,4,16). And of course the “Kirkman” problem, arranging the 20 elements of an S(2,4,16) into 5 partitions, each a S(1,4,16), is easily solved.

    Has this problem been solved, or proven insoluble? If not, do you have any insight that might help me find a solution?

  3. Michael Steyer says:

    Thanks a lot for the elegant solution and understandable explanation of factor 2-cover construction! This settles parts of a question that I posed myself 30 years ago when I designed soccer tournaments at high school. We were 8 boys and wanted to play a tournament with 4 teams each day so that each pair of players plays vs each other pair of players exactly once. I spent some classes with trying to find a design – of course in vain because there is no solution.

    Many years later I rediscovered this problem, renamed it doubles tennis tournament design and found a solution for 10 players, first by something like brute force on a PC, later by design. I think that solution is not isomorphic to the one described here: I started with 8 players and designed 7 days by taking pairs of players from adjacent columns from the addition table of GF(8), adding (9,10) to each day. Then I left 10 at its place and permuted players 1-9 according to the rows of the addition table of GF(9). I wonder whether this is of any interest – in particular because this method seems to fail for n=18 – but I can provide details on request.

  4. Futamarka says:

    Он сбежал из дворца, и от женщин, и от богатств, и от роскоши, от всего… Поэтому я не против Зорбы-Грека, потому что Зорба-Грек — это сама основа Зорбы-Будды. Будда вырастает из этого опыта. Я целиком за этот мир, потому что я знаю, что другой мир может быть почувствован только через этот. Поэтому я не говорю, что его следует избегать, я не скажу вам: станьте монахом. Монах — это тот, кто пошел против Зорбы, он беглец, трус; он сделал что-то в спешке, неразумно. Он незрелый человек. Монах — неспелый, жадный — жаждущий иного мира, и хочет его слишком рано, а время еще не пришло, монах еще не созрел.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s