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
Translated by:
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

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?)

  • 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 $19$ 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 $15$ 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 $15$, 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 $1.5$), Technical Report TR-CS-90-02, Computer Science Department, Australian National University, 1990.
  • 14. B. D. McKay, autoson - a distributed batch system for UNIX workstation networks (version $1.3$), Technical Report TR-CS-96-03, Computer Science Department, Australian National University, 1996.
  • 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, $2000000$ Steiner triple systems of order $19$, Math. Comp. 44 (1985), 533-535. MR 86e:05014
  • 20. D. R. Stinson and E. Seah, $284\,457$ Steiner triple systems of order $19$ contain a subsystem of order $9$, 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

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

American Mathematical Society