Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The Steiner triple systems of order 19

Authors: Petteri Kaski and Patric R. J. Östergård
Journal: Math. Comp. 73 (2004), 2075-2092
MSC (2000): Primary 05B07; Secondary 05E30, 51E10, 68R10
Published electronically: January 5, 2004
MathSciNet review: 2059752
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Using an orderly algorithm, the Steiner triple systems of order $19$ are classified; there are $11,\!084,\!874,\!829$ pairwise nonisomorphic such designs. For each design, the order of its automorphism group and the number of Pasch configurations it contains are recorded; $2,\!591$ of the designs are anti-Pasch. There are three main parts of the classification: constructing an initial set of blocks, the seeds; completing the seeds to triple systems with an algorithm for exact cover; and carrying out isomorph rejection of the final triple systems. Isomorph rejection is based on the graph canonical labeling software nauty supplemented with a vertex invariant based on Pasch configurations. The possibility of using the (strongly regular) block graphs of these designs in the isomorphism tests is utilized. The aforementioned value is in fact a lower bound on the number of pairwise nonisomorphic strongly regular graphs with parameters $(57,24,11,9)$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 05B07, 05E30, 51E10, 68R10

Retrieve articles in all journals with MSC (2000): 05B07, 05E30, 51E10, 68R10

Additional Information

Petteri Kaski
Affiliation: Department of Computer Science and Engineering, Helsinki University of Technology, P.O. Box 5400, 02015 HUT, Finland

Patric R. J. Östergård
Affiliation: Department of Electrical and Communications Engineering, Helsinki University of Technology, P.O. Box 3000, 02015 HUT, Finland

Keywords: Automorphism group, orderly algorithm, Pasch configuration, Steiner triple system
Received by editor(s): December 21, 2001
Received by editor(s) in revised form: February 28, 2003
Published electronically: January 5, 2004
Additional Notes: The research was supported in part by the Academy of Finland under grants 44517 and 100500. The work of the first author was partially supported by Helsinki Graduate School in Computer Science and Engineering (HeCSE) and a grant from the Foundation of Technology, Helsinki, Finland (Tekniikan Edistämissäätiö)
Article copyright: © Copyright 2004 American Mathematical Society