A Steiner triple system of order
(STS
) is a set of triples, or blocks, constructed over a set of
points, such that every pair of distinct points occurs in a unique block.
Previously, a complete classification of the STS
up to isomorphism was known only for
. In this work, we classify by computer search the next open case,
. The classification proceeds in two stages. First, we construct an initial set of 25-block seed configurations. Then, using an algorithm for the exact cover problem, we determine all completions of the seeds to STS
. Isomorph rejection on the STS
is carried out using the graph canonical labelling package nauty supplemented with a vertex invariant based on Pasch configurations.
We conclude that there are
nonisomorphic STS
and study a number of their properties. In particular, the number of anti-Pasch STS
is
and the number of STS
with a nontrivial automorphism group is
.
We also develop an independent algorithm for classifying STS
with a prescribed group of automorphisms. We then use this algorithm to classify the STS
with a nontrivial automorphism group. The results obtained in this partial classification match those obtained in the main search.
Finally, we show that the main classification algorithm can be used with minor modifications to classify certain related combinatorial structures, such as latin squares and one-factorizations of complete graphs. We estimate the performance of the algorithm in classifying one-factorizations of the complete graph on
vertices.
classification algorithm, isomorph rejection, one-factorization, Pasch configuration, Steiner triple system
@phdthesis{Kaski:licthesis,
author = {Petteri Kaski},
month = {December},
school = {Helsinki University of Technology, Department of Computer Science and Engineering},
title = {A Census of {S}teiner Triple Systems and Some Related Combinatorial Objects},
type = {Licentiate's Thesis},
year = {2002},
}