The Steiner triple systems of order 19

Authors:
Petteri Kaski and Patric R. J. Östergård

Translated by:

Journal:
Math. Comp. **73** (2004), 2075-2092

MSC (2000):
Primary 05B07; Secondary 05E30, 51E10, 68R10

DOI:
https://doi.org/10.1090/S0025-5718-04-01626-6

Published electronically:
January 5, 2004

MathSciNet review:
2059752

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Using an orderly algorithm, the Steiner triple systems of order are classified; there are pairwise nonisomorphic such designs. For each design, the order of its automorphism group and the number of Pasch configurations it contains are recorded; 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 .

**1.**R. C. Bose,*Strongly regular graphs, partial geometries and partially balanced designs*, Pacific J. Math.**13**(1963), 389-419. MR**28:1137****2.**G. Butler,*Fundamental Algorithms for Permutation Groups*, Lecture Notes in Computer Science, Vol. 559, Springer-Verlag, Berlin, 1991. MR**94d:68049****3.**C. J. Colbourn, S. S. Magliveras, and D. R. Stinson,*Steiner triple systems of order with nontrivial automorphism group*, Math. Comp.**59**(1992), 283-295. MR**92k:05022****4.**C. J. Colbourn and A. Rosa,*Triple Systems*, Clarendon Press, Oxford, 1999. MR**2002h:05024****5.**F. N. Cole, L. D. Cummings, and H. S. White,*The complete enumeration of triad systems in elements*, Proc. Nat. Acad. Sci. U.S.A.**3**(1917), 197-199.**6.**G. P. Egorychev,*The solution of van der Waerden's problem for permanents*, Adv. in Math.**42**(1981), 299-305. MR**83b:15002b****7.**D. I. Falikman,*Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix (in Russian)*, Mat. Zametki**29**(1981), 931-938, 957. MR**82k:15007****8.**M. J. Grannell, T. S. Griggs, and E. Mendelsohn,*A small basis for four-line configurations in Steiner triple systems*, J. Combin. Des.**3**(1995), 51-59. MR**95j:05041****9.**B. D. Gray and C. Ramsay,*On the number of Pasch configurations in a Steiner triple system*, Bull. Inst. Combin. Appl.**24**(1998), 105-112. MR**99c:05030****10.**M. Hall, Jr. and J. D. Swift,*Determination of Steiner triple systems of order*, Math. Tables Aids Comput.**9**(1955), 146-152. MR**18:192d****11.**D. E. Knuth,*Dancing links*, Millennial Perspectives in Computer Science, J. Davies, B. Roscoe, and J. Woodcock, editors, Palgrave, Houndmills, 2000, pp. 187-214.**12.**B. D. McKay,*Practical graph isomorphism*, Congr. Numer.**30**(1981), 45-87. MR**83e:05061****13.**B. D. McKay,*nauty user's guide (version )*, Technical Report TR-CS-90-02, Computer Science Department, Australian National University, 1990.**14.**B. D. McKay,, Technical Report TR-CS-96-03, Computer Science Department, Australian National University, 1996.`autoson`- a distributed batch system for UNIX workstation networks (version )**15.**B. D. McKay,*Isomorph-free exhaustive generation*, J. Algorithms**26**(1998), 306-324. MR**98k:68132****16.**J. P. Murphy,*Steiner Triple Systems and Cycle Structure*, Ph.D. thesis, University of Central Lancashire, 1999.**17.**D. A. Spielman,*Faster isomorphism testing of strongly regular graphs*, Proc. 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, 22-24 May 1996, pp. 576-584. MR**97g:68005****18.**D. R. Stinson,*A comparison of two invariants for Steiner triple systems: Fragments and trains*, Ars. Combin.**16**(1983), 69-76. MR**85f:05023****19.**D. R. Stinson and H. Ferch,*Steiner triple systems of order*, Math. Comp.**44**(1985), 533-535. MR**86e:05014****20.**D. R. Stinson and E. Seah,*Steiner triple systems of order contain a subsystem of order*, Math. Comp.**46**(1986), 717-729. MR**87c:05027****21.**D. R. Stinson and Y. J. Wei,*Some results on quadrilaterals in Steiner triple systems*, Discrete Math.**105**(1992), 207-219. MR**93h:05021****22.**H. S. White, F. N. Cole, and L. D. Cummings,*Complete classification of triad systems on fifteen elements*, Memoirs Nat. Acad. Sci. U.S.A.**14**(1919), 1-89.**23.**R. M. Wilson,*Nonisomorphic Steiner triple systems*, Math. Z.**135**(1974), 303-313. MR**49:4803**

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

Email:
petteri.kaski@hut.fi

**Patric R. J. Östergård**

Affiliation:
Department of Electrical and Communications Engineering, Helsinki University of Technology, P.O. Box 3000, 02015 HUT, Finland

Email:
patric.ostergard@hut.fi

DOI:
https://doi.org/10.1090/S0025-5718-04-01626-6

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