The Steiner triple systems of order 19

Kaski, Petteri; Östergård, Patric

doi:10.1090/S0025-5718-04-01626-6

The Steiner triple systems of order 19
HTML articles powered by AMS MathViewer

by Petteri Kaski and Patric R. J. Östergård PDF

Math. Comp. 73 (2004), 2075-2092 Request permission

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

R. C. Bose, Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math. 13 (1963), 389–419. MR 157909, DOI 10.2140/pjm.1963.13.389
G. Butler, Fundamental algorithms for permutation groups, Lecture Notes in Computer Science, vol. 559, Springer-Verlag, Berlin, 1991. MR 1225579, DOI 10.1007/3-540-54955-2
Charles J. Colbourn, Spyros S. Magliveras, and D. R. Stinson, Steiner triple systems of order $19$ with nontrivial automorphism group, Math. Comp. 59 (1992), no. 199, 283–295, S25–S27. MR 1134722, DOI 10.1090/S0025-5718-1992-1134722-8
Charles J. Colbourn and Alexander Rosa, Triple systems, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1999. MR 1843379
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.
G. P. Egorychev, Proof of the van der Waerden conjecture for permanents, Sibirsk. Mat. Zh. 22 (1981), no. 6, 65–71, 225 (Russian). MR 638007
D. I. Falikman, Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix, Mat. Zametki 29 (1981), no. 6, 931–938, 957 (Russian). MR 625097
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), no. 1, 51–59. MR 1305447, DOI 10.1002/jcd.3180030107
Brenton D. Gray and Colin Ramsay, On the number of Pasch configurations in a Steiner triple system, Bull. Inst. Combin. Appl. 24 (1998), 105–112. MR 1641476
Cahit Arf, Untersuchungen über reinverzweigte Erweiterungen diskret bewerteter perfekter Körper, J. Reine Angew. Math. 181 (1939), 1–44 (German). MR 18, DOI 10.1515/crll.1940.181.1
D. E. Knuth, Dancing links, Millennial Perspectives in Computer Science, J. Davies, B. Roscoe, and J. Woodcock, editors, Palgrave, Houndmills, 2000, pp. 187–214.
Brendan D. McKay, Practical graph isomorphism, Congr. Numer. 30 (1981), 45–87. MR 635936
B. D. McKay, nauty user’s guide (version $1.5$), Technical Report TR-CS-90-02, Computer Science Department, Australian National University, 1990.
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.
Brendan D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998), no. 2, 306–324. MR 1606516, DOI 10.1006/jagm.1997.0898
J. P. Murphy, Steiner Triple Systems and Cycle Structure, Ph.D. thesis, University of Central Lancashire, 1999.
Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing, ACM Press, New York, 1996. Held in Philadelphia, PA, May 22–24, 1996. MR 1427491
D. R. Stinson, A comparison of two invariants for Steiner triple systems: fragments and trains, Ars Combin. 16 (1983), 69–76. MR 734047
D. R. Stinson and H. Ferch, $2\,000\,000$ Steiner triple systems of order $19$, Math. Comp. 44 (1985), no. 170, 533–535. MR 777284, DOI 10.1090/S0025-5718-1985-0777284-3
D. R. Stinson and E. Seah, $284\,457$ Steiner triple systems of order $19$ contain a subsystem of order $9$, Math. Comp. 46 (1986), no. 174, 717–729. MR 829642, DOI 10.1090/S0025-5718-1986-0829642-7
D. R. Stinson and Y. J. Wei, Some results on quadrilaterals in Steiner triple systems, Discrete Math. 105 (1992), no. 1-3, 207–219. MR 1180204, DOI 10.1016/0012-365X(92)90143-4
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.
Richard M. Wilson, Nonisomorphic Steiner triple systems, Math. Z. 135 (1973/74), 303–313. MR 340046, DOI 10.1007/BF01215371