Enumeration of Steiner triple systems with subsystems
HTML articles powered by AMS MathViewer
- by Petteri Kaski, Patric R. J. Östergård and Alexandru Popa PDF
- Math. Comp. 84 (2015), 3051-3067 Request permission
Abstract:
A Steiner triple system of order $v$, an STS($v$), is a set of $3$-element subsets, called blocks, of a $v$-element set of points, such that every pair of distinct points occurs in exactly one block. A subsystem of order $w$ in an STS($v$), a sub-STS($w$), is a subset of blocks that forms an STS($w$). Constructive and nonconstructive techniques for enumerating up to isomorphism the STS($v$) that admit at least one sub-STS($w$) are presented here for general parameters $v$ and $w$. The techniques are further applied to show that the number of isomorphism classes of STS($21$)s with at least one sub-STS($9$) is $12661527336$ and of STS($27$)s with a sub-STS($13$) is $1356574942538935943268083236$.References
- Majid Behbahani, Clement Lam, and Patric R. J. Östergård, On triple systems and strongly regular graphs, J. Combin. Theory Ser. A 119 (2012), no. 7, 1414–1426. MR 2925933, DOI 10.1016/j.jcta.2012.03.013
- G. Brunel, Sur les deux systèmes de triades de trieze éléments, Journal de Mathématiques Pures et Appliquées, Cinquième Série 7 (1901), 305–330.
- C. J. Colbourn, J. H. Dinitz, and I. M. Wanless, Latin squares, In C. J. Colbourn and J. H. Dinitz, editors, Handbook of Combinatorial Designs, pages 135–152. Chapman & Hall/CRC, Boca Raton, FL, 2007.
- Charles J. Colbourn, Anthony D. Forbes, Mike J. Grannell, Terry S. Griggs, Petteri Kaski, Patric R. J. Östergård, David A. Pike, and Olli Pottonen, Properties of the Steiner triple systems of order 19, Electron. J. Combin. 17 (2010), no. 1, Research Paper 98, 30. MR 2661401
- Charles J. Colbourn, Monica A. Oravas, and Rolf S. Rees, Steiner triple systems with disjoint or intersecting subsystems, J. Combin. Des. 8 (2000), no. 1, 58–77. MR 1728889, DOI 10.1002/(SICI)1520-6610(2000)8:1<1::AID-JCD1>3.0.CO;2-N
- 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, Proceedings of the National Academy of Sciences of the United States of America, 3 (1917), 197–199.
- V. De Pasquale, Sui sistemi ternari di $13$ elementi, Rendiconti. Reale Istituto Lombardo di Science e Lettere. Serie II. 32 (1899), 213–221.
- R. Déherder, Recouvrements, PhD thesis, Université Libre de Bruxelles, 1976.
- Jean Doyen and Richard M. Wilson, Embeddings of Steiner triple systems, Discrete Math. 5 (1973), 229–239. MR 327539, DOI 10.1016/0012-365X(73)90139-8
- I. A. Faradžev, Constructive enumeration of combinatorial objects, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 131–135 (English, with French summary). MR 539959
- Alexander Hulpke, Petteri Kaski, and Patric R. J. Östergård, The number of Latin squares of order 11, Math. Comp. 80 (2011), no. 274, 1197–1219. MR 2772119, DOI 10.1090/S0025-5718-2010-02420-2
- Petteri Kaski and Patric R. J. Östergård, There exists no $(15,5,4)$ RBIBD, J. Combin. Des. 9 (2001), no. 5, 357–362. MR 1849618, DOI 10.1002/jcd.1016
- Petteri Kaski and Patric R. J. Östergård, The Steiner triple systems of order 19, Math. Comp. 73 (2004), no. 248, 2075–2092. MR 2059752, DOI 10.1090/S0025-5718-04-01626-6
- Petteri Kaski and Patric R. J. Östergård, One-factorizations of regular graphs of order 12, Electron. J. Combin. 12 (2005), Research Paper 2, 25. MR 2134165
- Petteri Kaski and Patric R. J. Östergård, Classification algorithms for codes and designs, Algorithms and Computation in Mathematics, vol. 15, Springer-Verlag, Berlin, 2006. With 1 DVD-ROM (Windows, Macintosh and UNIX). MR 2192256
- Petteri Kaski and Patric R. J. Östergård, There are $1,132,835,421,602,062,347$ nonisomorphic one-factorizations of $K_{14}$, J. Combin. Des. 17 (2009), no. 2, 147–159. MR 2489440, DOI 10.1002/jcd.20188
- Petteri Kaski, Patric R. J. Östergård, Svetlana Topalova, and Rosen Zlatarski, Steiner triple systems of order 19 and 21 with subsystems of order 7, Discrete Math. 308 (2008), no. 13, 2732–2741. MR 2413971, DOI 10.1016/j.disc.2006.06.038
- Adalbert Kerber, Applied finite group actions, 2nd ed., Algorithms and Combinatorics, vol. 19, Springer-Verlag, Berlin, 1999. MR 1716962, DOI 10.1007/978-3-662-11167-3
- D. E. Knuth, Dancing links, In J. Davies, B. Roscoe, and J. Woodcock, editors, Millennial Perspectives in Computer Science, pages 187–214, Palgrave, Basingstoke, England, 2000.
- R. Mathon and A. Rosa, 2-$(v,k,\lambda )$ designs of small order, In C. J. Colbourn and J. H. Dinitz, editors, Handbook of Combinatorial Designs, pages 25–58. Chapman & Hall/CRC, Boca Raton, FL, 2007.
- B. D. McKay. nauty User’s Guide (Version 1.5), Technical Report TR-CS-90-02, Computer Science Department, Australian National University, Canberra, 1990.
- Brendan D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998), no. 2, 306–324. MR 1606516, DOI 10.1006/jagm.1997.0898
- Brendan D. McKay, Alison Meynert, and Wendy Myrvold, Small Latin squares, quasigroups, and loops, J. Combin. Des. 15 (2007), no. 2, 98–119. MR 2291523, DOI 10.1002/jcd.20105
- Ronald C. Read, Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations, Ann. Discrete Math. 2 (1978), 107–120. MR 491273
- N. V. Semakov and V. A. Zinov′ev, Equidistant $q$-ary codes with maximal distance and resolvable balanced incomplete block designs, Problems Inform. Transmission 4 (1968), no. 2, 1–7 (1971). MR 347445
- 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
- H. S. White, F. N. Cole, and L. D. Cummings, Complete classification of triad systems on fifteen elements, Memoirs of the National Academy of Sciences 14 (1919) no. 2, 1–89.
Additional Information
- Petteri Kaski
- Affiliation: Helsinki Institute for Information Technology HIIT, Department of Information and Computer Science, Aalto University, P.O. Box 15400, 00076 Aalto, Finland
- Patric R. J. Östergård
- Affiliation: Department of Communications and Networking, Aalto University School of Electrical Engineering, P.O. Box 13000, 00076 Aalto, Finland
- Alexandru Popa
- Affiliation: Department of Communications and Networking, Aalto University School of Electrical Engineering, P.O. Box 13000, 00076 Aalto, Finland
- Received by editor(s): November 19, 2013
- Received by editor(s) in revised form: March 4, 2014
- Published electronically: April 7, 2015
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 84 (2015), 3051-3067
- MSC (2010): Primary 05B07, 51E10
- DOI: https://doi.org/10.1090/mcom/2945
- MathSciNet review: 3378862