Salta al contenuto principale
Passa alla visualizzazione normale.

MARCO PAVONE

On the seven non-isomorphic solutions of the fifteen schoolgirl problem

Abstract

In this paper we give a simple and effective tool to analyze a given Kirkman triple system of order 15 and determine which of the seven well-known non-isomorphic KTS(15)s it is isomorphic to. Our technique refines and improves the lacing of distinct parallel classes introduced by F. N. Cole, by means of the notion of residual triple defined by G. Falcone and the present author in a previous paper. Unlike Cole's original lacing scheme, our algorithm allows one to distinguish two KTS(15)s also in the harder case where the two systems have the same underlying Steiner triple system. In the special case where the common STS is #19, an alternative method is given by means of the 1-factorizations of the complete graph K_8 associated to the two KTSs. Moreover, we present three new visual solutions to the schoolgirl problem, and we catalogue most of the classical (or interesting) solutions in the literature in terms of what KTS(15)s they are isomorphic to. This paper provides background on a classical topic, while shedding new light on the problem as well.