Biembeddability of Steiner triple systems

Mike Grannell and Terry Griggs from the Combinatorics Research Group, working with Martin Knor from the Slovak Technical University in Bratislava, have been investigating the biembeddability of Steiner triple systems of order 15 in an orientable surface.

Basically the idea is to take a sphere with a number of handles attached, to place points ("vertices") on this surface and join them by lines ("edges") also on the surface so that the edges only intersect at the vertices, every vertex is joined to every other vertex by a unique edge, and the resulting faces are all triangular (i.e. they all have exactly three edges). If, in addition, it is possible to colour the faces black and white so that no two faces of the same colour have a common edge, then the faces in each colour class form a Steiner triple system of order n, where n is the number of vertices. The two Steiner triple systems are said to be biembedded in the surface.

A Steiner triple system of order n is a set of triples taken from a set of n points with the property that each pair of the points appears in exactly one triple. So in a biembedding, the faces in each colour class form the triples and the edges form the pairs. Such biembeddings are only possible if n has the form 12s+3 or 12s+7 for s=1, 2, 3, . . ., and the cases n=3 and n=7 are trivial. So the first really interesting and difficult case is n=15, and in this case the sphere must have eleven handles

There are 80 essentially different Steiner triple systems of order 15 and it is a mammoth job to determine which pairs can be biembedded. For five of the systems that have particularly amenable structures, we have already determined the systems with which they can be biembedded. This work, which is to be published in the Journal of Combinatorial Mathematics and Combinatorial Computing, was carried out sequentially on ordinary PC equipment, but it took many weeks. A full sequential run for all 80 systems on a PC would take well over a year. So now we are about to run a parallel search on the remaining 75 systems using the IMPACT research cluster and we hope that this will enable us to get the definitive answers within a reasonable period.

Running in parallel the calculations are completed in under three months. M. J. Grannell, T. S. Griggs, M. Knor and A. R. W. Thrower, A census of the orientable biembeddings of Steiner triple systems of order 15, Australasian Journal of Combinatorics 42, 25 details these results. Further parallel use of the cluster is planned.