2. Blogging
3. Nov 15, 2015

After several weeks of guest speakers in our Friday Afternoon Mathematics Undergraduate Seminar (FAMUS), I gave a short talk on Friday, November 13 that was centered around The Kirkman Schoolgirls Problem. In 1850, the Reverend Thomas Kirkman, posed an innocent-looking puzzle in the Lady’s and Gentleman’s Diary, a recreational mathematics journal:

Here “abreast” means “in a group,” so the girls are walking out in groups of three, and each pair of girls should only be in the same group once. It turns out that this problem is harder than it looks. It’s not even obvious that a solution is possible. In order to gain some insight into Kirkman’s problem, we tinkered with the following simpler problems.

Simpler Problem 1

Simpler Problem 2

Simpler Problem 3

The audience was able to quickly determine that the answer is “no” for problems 1 and 2. For the third problem, I let the audience play around for a bit and then I showed them one possible solution using Quanta Magazine’s applet located here. After discussing what it would take to verify that a proposed solution to Kirkman’s problem was actually a solution, I showed them one of seven possible solutions.

It turns out that Kirkman’s puzzle is a prototype for a more general problem:

Such an arrangement is said to be of type $S(t,k,n)$, which is called a Steiner systems (or combinatorial design theory). For example, solutions to the original Kirkman problem are of type $S(2,3,15)$. Notice that we have abandoned the extra restriction that the sets of size $k$ are sortable into days.

One of the fundamental problems in the theory of combinatorial designs is determining whether a given $S(t,k,n)$ exists and if one exists, how many are there? For example, is $S(2,3,7)$ possible? The answer is yes and one can interpret the Fano plane as one possible solution.

Many combinations of $t, k$, and $n$ can be quickly ruled out by divisibility obstacles. For example, problem 2 above helped us to determine that $S(2,3,6)$ is not possible. For combinations that aren’t immediately tossed out, there’s no easy way to discover whether a given combination is possible. For example, it turns out that $S(2,7,43)$ is impossible, but it is for complicated reasons. However, in January 2014, Peter Keevash (Oxford) established that, apart from a few exceptions, $S(t,k,n)$ will always exist if a few divisibility requirements are satisfied. This is a big deal in the world of combinatorial design theory.

As with many of the topics I choose to give a talk on in FAMUS, I pretty much knew nothing about the topic before I started prepping for the talk. I go out of my way to emphasize that this is the case because I want the students to know that the learning never ends.

Here are the slides for my talk. Note: There are two additional problems related to Kirkman’s problem at the very end that you might find interesting.

The content of my slides was inspired or came directly from the following sources:

• There is a great write up of Kirkman’s original problem, its connection to CDT, and a brief summary of Keevash’s new result in Quanta Magazine.
• The Wikipedia article on The Kirkman Schoolgirl Problem has a lot of cool information.
• Also, check out the Wikipedia articles on Steiner systems, Combinatorial Design Theory, and the Fano plane.
• You can find Peter Keevash’s article about the existence of Steiner systems over on the arXiv.

Most weeks in FAMUS, the host interviews a faculty member. However, this week, Dr. Derek Sonderegger gave a 30 minute talk on the merits of pursuing a graduate degree in mathematics, statistics, or mathematics education. In addition, Derek provided some details about our graduate program. We also had quite a few of our grad students in attendance that were able to chime in about their current experience.