On the structure of cyclic Steiner triple systems of small order
DOI:
https://doi.org/10.55630/mem.2026.55.433-441Keywords:
combinatorial design, Steiner Triple system, configurationAbstract
An n-configuration is a collection of n blocks of a particular STS(v). An n-configuration is full if none of its points occur in just one block. Of special interest for understanding the structure of an STS(v) is the number of its full configurations with no more than n + 2 points. An STS(v) is n-sparse if every set of i blocks covers more than i + 2 points, 4 <= i <= n. The first examples of 6-sparse STS(v)s were presented by Forbes, Grannell and Griggs in 2007. The smallest known 6-sparse STS(v) is of order 139. Recently the properties of all STS(19)s were analyzed by Colbourn and coauthors, 2010 and of STS(21)s with nontrivial automorphisms by Erskine, Griggs, 2024 and 6-sparse STS(v)s were not found among them. It is not known if there exists a 6-sparse STS(v) for some order smaller than 139. In an attempt to answer this question we count the number of the full 6-configurations with 8 points in cyclic STS(v)s of small order. There are no 6-sparse ones but we find some examples of STS(v)s, 25 <= v <= 63 with interesting structure.
References
M. ASIF, W. ZHOU, M. AJMAL, Z. UL A. AKHTAR, and N. A. KHAN. A construction of high performance quasicyclic LDPC codes: a combinatoric design approach. Wireless Communications and Mobile Computing:7468792, 2019.
T. BAICHEVA and S. TOPALOVA. Classification results for (v, k, 1) cyclic difference families with small parameters. In M. DEZA, M. PETITJEAN, and K. MARKOV, editors, Mathematics of Distances and Applications. Volume 25, Information Science and Computing, pages 24–30. 2012.
A. E. BROUWER. Steiner Triple Systems without Forbidden Subconfigurations. Technical report ZW104/77, Mathematisch Centrum Amsterdam, 1977.
C. J. COLBOURN and J. H. DINITZ, editors. Handbook of Combinatorial Designs. CRC Press, Boca Raton, 2nd edition, 2007.
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. Electronic Journal of Combinatorics, 17:R98, 2010.
C. J. COLBOURN, E. MENDELSOHN, A. ROSA, and J. ŠIRÁŇ. Anti-mitre Steiner triple systems. Graphs and Combinatorics, 10:215–224, 1994.
C. J. COLBOURN and A. ROSA. Triple Systems. Clarendon Press, Oxford, 1999.
P. ERDŐS. Problems and results in combinatorial analysis. Colloquia Mathematica Societatis János Bolyai, 9:25, 1976.
G. ERSKINE and T. S. GRIGGS. Properties of Steiner triple systems of order 21. Discrete Mathematics, 347(11):114–158, 2024.
A. D. FORBES, M. J. GRANNELL, and T. S. GRIGGS. Configurations and trades in Steiner triple systems. Australasian Journal of Combinatorics, 29:75–84, 2004.
A. D. FORBES, M. J. GRANNELL, and T. S. GRIGGS. On 6-sparse Steiner triple systems. Journal of Combinatorial Theory, Series A, 114(2):235–252, 2007.
A. D. FORBES, M. J. GRANNELL, and T. S. GRIGGS. Further 6-sparse Steiner triple systems. Graphs and Combinatorics, 25:49–64, 2009.
Y. FUJIWARA. Infinite classes of anti-mitre and 5-sparse Steiner triple systems. Journal of Combinatorial Designs, 14:237–250, 2006.
Y. FUJIWARA. Sparseness of triple systems: a survey. In Theory and Applications of Combinatorial Designs with Related Field, volume 1465 of RIMS Kokyuroku, pages 173–185, Kyoto, 2006.
Y. FUJIWARA. Nonexistence of sparse triple systems over abelian groups and involutions. Journal of Algebraic Combinatorics, 26(4):495–506, 2007.
M. J. GRANNELL and T. S. GRIGGS. Configurations in Steiner triple systems. In F. C. HOLROYD, K. A. S. QUINN, C. ROWLEY, and B. S. WEBB, editors, Combinatorial Designs and Their Applications, pages 103–126. Chapman and Hall/CRC, Boca Raton, 1999.
M. J. GRANNELL, T. S. GRIGGS, and C. A. WHITEHEAD. The resolution of the anti-Pasch conjecture. Journal of Combinatorial Designs, 8(4):300–309, 2000.
A. GRUNER and M. HUBER. New combinatorial construction techniques for low-density paritycheck codes and systematic repeat-accumulate codes. IEEE Transactions on Communications, 60(9):2387–2395, 2012.
D. HEINLEIN and P. R. J. ÖSTERGÅRD. Algorithms and complexity for counting configurations in Steiner triple systems. Journal of Combinatorial Designs, 30:527–546, 2022.
I. HETMAN, T. BAICHEVA, and S. TOPALOVA. Construction of (v, k, 1) cyclic difference families with small parameters. Journal of Algebra, Combinatorics, Discrete Structures and Applications, 13(1):111–119, 2026.
P. HORAK, N. K. C. PHILLIPS, W. D. WALLIS, and J. L. YUCAS. Counting frequencies of configurations in Steiner triple systems. Ars Combinatoria, 46:65–75, 1997.
J. I. KOKKALA and P. R. J. ÖSTERGÅRD. Sparse Steiner triple systems of order 21. Journal of Combinatorial Designs, 29(2):75–83, 2021.
D. J. C. MACKAY. Good error-correcting codes based on very sparse matrices. IEEE Transactions on Information Theory, 45(2):399–431, 1999.
H. PARK, S. HONG, J.-S. NO, and D.-J. SHIN. Design of multiple-edge protographs for QC LDPC codes avoiding short inevitable cycles. IEEE Transactions on Information Theory, 59(7):4598–4614, 2013.
D. R. STINSON and Y. J. WEI. Some results on quadrilaterals in Steiner triple systems. Discrete Mathematics, 105(1–3):207–219, 1992.
A. TSVETANOVA and S. ZHELEZOVA. Useful configurations in cyclic Steiner triple systems of small order, 2025. To appear in Studies in Computational Intelligence.
B. VASIC and O. MILENKOVIC. Combinatorial constructions of low-density parity-check codes for iterative decoding. IEEE Transactions on Information Theory, 50:1156–1176, 2004.
A. WOLFE. The resolution of the anti-mitre Steiner triple system conjecture. Journal of Combinatorial Designs, 14:229–236, 2006.
A. WOLFE. The existence of 5-sparse Steiner triple systems of order n equiv 3 (mod 6), n = {9, 15}. Journal of Combinatorial Theory, Series A, 115(8):1487–1503, 2008.
