Enumeration of steiner triple systems with subsystems

Petteri Kaski, Patric R J östergård, Alexandru Popa

Research output: Contribution to journalArticle

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.

Original languageEnglish
Pages (from-to)3051-3067
Number of pages17
JournalMathematics of Computation
Volume84
Issue number296
DOIs
Publication statusPublished - 2015

Fingerprint

Steiner Triple System
Enumeration
Subsystem
Subset
Isomorphism Classes
Set of points
Isomorphism
Distinct

Keywords

  • Classification
  • Enumeration
  • Steiner triple system
  • Subsystem

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Computational Mathematics
  • Applied Mathematics

Cite this

Kaski, P., östergård, P. R. J., & Popa, A. (2015). Enumeration of steiner triple systems with subsystems. Mathematics of Computation, 84(296), 3051-3067. https://doi.org/10.1090/mcom/2945

Enumeration of steiner triple systems with subsystems. / Kaski, Petteri; östergård, Patric R J; Popa, Alexandru.

In: Mathematics of Computation, Vol. 84, No. 296, 2015, p. 3051-3067.

Research output: Contribution to journalArticle

Kaski, P, östergård, PRJ & Popa, A 2015, 'Enumeration of steiner triple systems with subsystems', Mathematics of Computation, vol. 84, no. 296, pp. 3051-3067. https://doi.org/10.1090/mcom/2945
Kaski, Petteri ; östergård, Patric R J ; Popa, Alexandru. / Enumeration of steiner triple systems with subsystems. In: Mathematics of Computation. 2015 ; Vol. 84, No. 296. pp. 3051-3067.
@article{8562dcdaae18408dae12cf40fec64aff,
title = "Enumeration of steiner triple systems with subsystems",
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.",
keywords = "Classification, Enumeration, Steiner triple system, Subsystem",
author = "Petteri Kaski and {\"o}sterg{\aa}rd, {Patric R J} and Alexandru Popa",
year = "2015",
doi = "10.1090/mcom/2945",
language = "English",
volume = "84",
pages = "3051--3067",
journal = "Mathematics of Computation",
issn = "0025-5718",
publisher = "American Mathematical Society",
number = "296",

}

TY - JOUR

T1 - Enumeration of steiner triple systems with subsystems

AU - Kaski, Petteri

AU - östergård, Patric R J

AU - Popa, Alexandru

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Classification

KW - Enumeration

KW - Steiner triple system

KW - Subsystem

UR - http://www.scopus.com/inward/record.url?scp=85000766794&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85000766794&partnerID=8YFLogxK

U2 - 10.1090/mcom/2945

DO - 10.1090/mcom/2945

M3 - Article

AN - SCOPUS:85000766794

VL - 84

SP - 3051

EP - 3067

JO - Mathematics of Computation

JF - Mathematics of Computation

SN - 0025-5718

IS - 296

ER -