TCS / Research / Publications / A Census of Steiner Triple Systems and Some Related Combinatorial Objects
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

A Census of Steiner Triple Systems and Some Related Combinatorial Objects

Reference:

Petteri Kaski. A Census of Steiner Triple Systems and Some Related Combinatorial Objects. Licentiate's thesis, Helsinki University of Technology, Department of Computer Science and Engineering, December 2002.

Abstract:

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.

Keywords:

classification algorithm, isomorph rejection, one-factorization, Pasch configuration, Steiner triple system

Suggested BibTeX entry:

@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},
}

This work is not available online here.

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.