|
The Steiner triple systems of order 19
Author(s):
Petteri
Kaski;
Patric
R. J.
Östergård.
Journal:
Math. Comp.
73
(2004),
2075-2092.
MSC (2000):
Primary 05B07;
Secondary 05E30, 51E10, 68R10
Posted:
January 5, 2004
Retrieve article in:
PDF
This article is available free of charge
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  .
References:
-
- 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, autoson - a distributed batch system for UNIX workstation networks (version
 ), 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,
 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
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
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:
10.1090/S0025-5718-04-01626-6
PII:
S 0025-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
Posted:
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ö)
Copyright of article:
Copyright
2004,
American Mathematical Society
|
Comments: webmaster@ams.org