Combinatorial Success for High Performance Computing Cluster

Wednesday, Mar 12th 2008

A major success for the MCT Faculty's Linux High Performance Computing (HPC) cluster has been the determination of all 9,530 orientable biembeddings of Steiner triple systems of order 15 (STS(15)s).

There are 80 genuinely distinct ("nonisomorphic") STS(15)s. Each consists of 35 triples of points drawn from a base set of 15 points. The 35 triples have the property that each pair of points lies in exactly one triple. If we take two of these systems and represent the triples as triangles, black for one system and white for the other, we can sew the triangles together along their common edges. Then each point is represented as vertex and each pair as an edge bordering a black triangle on one side and a white triangle on the other. This gets really interesting in the rare cases when, in the resulting surface, each vertex is surrounded by a single cycle of 14 alternately black and white triangles, rather than several cycles of combined length 14. These interesting cases are called biembeddings of the two systems. The surface may be orientable (meaning roughly that it has an inside and an outside, like a hollow sphere or hollow torus) or nonorientable (meaning that it is single-sided, like a Möbius band).

An OU team, augmented by Martin Knor from the Slovak Technical University, enumerated all the nonisomorphic orientable biembeddings. At first sight it appears necessary to examine 15!=1,307,674,368,000 possibilities. But careful consideration of the individual systems reduces that number considerably. Each system was allocated to a separate processor in the Linux cluster, and determination of all the biembeddings of each system took between two and ten weeks. Without the cluster the whole job would have taken around nine years, and would probably have been infeasible. The expertise of cluster guru, Allan Thrower, was instrumental in keeping the whole operation together and dealing with the inevitable problem when a power-cut disrupted some of the runs. Fortunately the program had been written to cope with such events!

The results will appear in a paper in the Australasian Journal of Combinatorics, and a preprint is available here as a pdf file.

Report an error on this page