Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Enumeration of Steiner triple systems with subsystems


Authors: Petteri Kaski, Patric R. J. Östergård and Alexandru Popa
Journal: Math. Comp. 84 (2015), 3051-3067
MSC (2010): Primary 05B07, 51E10
DOI: https://doi.org/10.1090/mcom/2945
Published electronically: April 7, 2015
MathSciNet review: 3378862
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1016/j.jcta.2012.03.013
  • [2] 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.
  • [3] 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.
  • [4] C. J. Colbourn, A. D. Forbes, M. J. Grannell, T. S. Griggs, P. Kaski, P. R. J. Östergård, D. A. Pike, and O. Pottonen, Properties of the Steiner triple systems of order 19, Electron. J. Combin. 17 (2010), no. 1. MR 2661401 (2011g:05041)
  • [5] 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 (2000j:05021), https://doi.org/10.1002/(SICI)1520-6610(2000)8:1$ \langle $1::AID-JCD1$ \rangle $3.0.CO;2-N
  • [6] C. J. Colbourn and Alexander Rosa, Triple Systems, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1999. MR 1843379 (2002h:05024)
  • [7] 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.
  • [8] V. De Pasquale, Sui sistemi ternari di $ 13$ elementi, Rendiconti. Reale Istituto Lombardo di Science e Lettere. Serie II. 32 (1899), 213-221.
  • [9] R. Déherder, Recouvrements, PhD thesis, Université Libre de Bruxelles, 1976.
  • [10] Jean Doyen and Richard M. Wilson, Embeddings of Steiner triple systems, Discrete Math. 5 (1973), 229-239. MR 0327539 (48 #5881)
  • [11] 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 (80i:05049)
  • [12] 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 (2011m:05064), https://doi.org/10.1090/S0025-5718-2010-02420-2
  • [13] 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 (2002f:05030), https://doi.org/10.1002/jcd.1016
  • [14] 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 (2005b:05035), https://doi.org/10.1090/S0025-5718-04-01626-6
  • [15] 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 pp. (electronic). MR 2134165 (2005m:05179)
  • [16] 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 (2008a:05002)
  • [17] 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, https://doi.org/10.1002/jcd.20188
  • [18] 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 (2009f:05032), https://doi.org/10.1016/j.disc.2006.06.038
  • [19] Adalbert Kerber, Applied Finite Group Actions, 2nd ed., Algorithms and Combinatorics, vol. 19, Springer-Verlag, Berlin, 1999. MR 1716962 (2000j:05129)
  • [20] 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.
  • [21] 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.
  • [22] B. D. McKay.
    nauty User's Guide (Version 1.5), Technical Report TR-CS-90-02, Computer Science Department, Australian National University, Canberra, 1990.
  • [23] Brendan D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998), no. 2, 306-324. MR 1606516 (98k:68132), https://doi.org/10.1006/jagm.1997.0898
  • [24] 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 (2007j:05030), https://doi.org/10.1002/jcd.20105
  • [25] Ronald C. Read, Every one a winner; or how to avoid isomorphism search when cataloguing combinatorial configurations, Algorithmic aspects of combinatorics (Conf., Vancouver Island, B.C., 1976), 1978, pp. 107-120. MR 0491273 (58 #10537)
  • [26] N. V. Semakov and V. A. Zinov'ev, Equidistant $ q$-ary codes with maximal distance and resolvable balanced incomplete block designs, Problemy Peredači Informacii 4 (1968), no. 2, 3-10 (Russian); English transl., Problems of Information Transmission 4 (1968), no. 2, 1-7 (1971). MR 0347445 (49 #12165)
  • [27] 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 (87c:05027), https://doi.org/10.2307/2008010
  • [28] 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.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 05B07, 51E10

Retrieve articles in all journals with MSC (2010): 05B07, 51E10


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

DOI: https://doi.org/10.1090/mcom/2945
Keywords: Classification, enumeration, Steiner triple system, subsystem
Received by editor(s): November 19, 2013
Received by editor(s) in revised form: March 4, 2014
Published electronically: April 7, 2015
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society