За структурата на цикличните Щайнерови системи от тройки малък ред
DOI :
https://doi.org/10.55630/mem.2026.55.433-441Ключови думи :
комбинаторен дизайн, Щайнерова система от тройки, конфигурацияАбстракт
Колекция от n блока в Щайнерова система от тройки от ред v (STS(v)) се нарича n-конфигурация. Една n-конфигурация е пълна, ако никоя от точките ѝ не участва само в един блок. От специален интерес за разбиране на структурата на STS(v) е броят на пълните конфигурации с не повече от n + 2 точки, които тя притежава. STS(v) e n-sparse, ако всяко множество от i блока е инцидентно с повече от i + 2 точки, 4 <= i <= n. Първите примери на 6-sparse STS(v) са публикувани от Forbes, Grannell и Griggs през 2007. Най-малката известна 6-sparse STS(v) е от ред 139. Свойствата на всички STS(19) са анализирани през 2010 от Colbourn и съавтори и на STS(21) с нетривиални групи от автоморфизми от Erskine, Griggs, 2024. Не са намерени 6-sparse STS(v) между тях. Не се знае съществуват ли 6-sparse STS(v) от редове по-малки от 139. В опит да отговорим на този въпрос, изследваме броя на пълните 6-конфигурации с 8 точки в цикличните STS(v) от малък ред. Не намираме 6-sparse циклични STS(v), 25 <= v <= 63, но представяме някои примери с интересна структура.
Литература (библиография)
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.
