A Census of Steiner Triple Systems and Some Related Combinatorial Objects (2003)
AUTHORS:
Kaski Petteri
URL:
http://www.tcs.hut.fi/Publications/info/pkaski.Kaski:licthesis.shtml
INTERNALPDF:
internalpdf/HUT-TCS-A78.pdf
@techreport{ HUT-TCS-A78, author = "Kaski, Petteri", ps = "HUT-TCS-A78.ps", title = "A Census of {S}teiner Triple Systems and Some Related Combinatorial Objects", url = "http://www.tcs.hut.fi/Publications/info/pkaski.Kaski:licthesis.shtml", pages = "65", address = "Espoo, Finland", number = "A78", abstract = "A Steiner triple system of order $v$ (STS($v$)) is a set of triples, or blocks, constructed over a set of $v$ points, such that every pair of distinct points occurs in a unique block. \par Previously, a complete classification of the STS($v$) up to isomorphism was known only for $v\leq 15$. In this work, we classify by computer search the next open case, $v=19$. 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 \emph{nauty} supplemented with a vertex invariant based on Pasch configurations. \par We conclude that there are $11,\!084,\!874,\!829$ nonisomorphic STS(19) and study a number of their properties. In particular, the number of anti-Pasch STS(19) is $2,\!591$ and the number of STS(19) with a nontrivial automorphism group is $164,\!758$. \par 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. \par 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.", month = "June", flags = "copy", year = "2003", keywords = "classification algorithm, isomorph rejection, one-factorization, Pasch configuration, Steiner triple system", pdf = "HUT-TCS-A78.pdf", onlinenote = "Reprint of Licentiate's thesis; see URL below.", type = "Research Report", institution = "Helsinki University of Technology, Laboratory for Theoretical Computer Science" }