Enumeration of Steiner triple systems with subsystems

Kaski, Petteri; Östergård, Patric; Popa, Alexandru

doi:10.1090/mcom/2945

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.