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. Research Report A78, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, June 2003.

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(19). Isomorph rejection on the STS(19) is carried out using the graph canonical labelling package emphnauty supplemented with a vertex invariant based on Pasch configurations.

We conclude that there are nonisomorphic STS(19) and study a number of their properties. In particular, the number of anti-Pasch STS(19) is and the number of STS(19) with a nontrivial automorphism group is .

We also develop an independent algorithm for classifying STS(19) with a prescribed group of automorphisms. We then use this algorithm to classify the STS(19) 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 12 vertices.

Keywords:

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

Suggested BibTeX entry:

@techreport{HUT-TCS-A78,
    address = {Espoo, Finland},
    author = {Petteri Kaski},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {June},
    number = {A78},
    pages = {65},
    title = {A Census of {S}teiner Triple Systems and Some Related Combinatorial Objects},
    type = {Research Report},
    year = {2003},
}

NOTE: Reprint of Licentiate's thesis; see URL below.
See www.tcs.hut.fi ...

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