Namespaces
Variants
Actions

Steiner triple system

From Encyclopedia of Mathematics
Jump to: navigation, search

A Steiner system $\mathrm{S}(2,3,n)$, that is, a set of size $n$ with a distinguished collection of subsets of size $3$ ("blocks") such that every subset of size $2$ is contained in exactly one block; denoted $\mathrm{STS}(n)$. Such a system exists if and only if $n \equiv 1,3 \pmod 6$: this was already established by Revd T.P. Kirkman in 1846.

The projective plane $\mathrm{P}(2,2)$ of order $2$, consisting of $7$ points and $7$ lines each containing $3$ points, in which any two points determine a unique line, is an $\mathrm{STS}(7)$.

A resolution of a design is a partition of its blocks into "parallel" classes, such that element of the underlying set is contained in just one block of each class: a resolvable design is one with a resolution. A resolvable Steiner triple system is a Kirkman triple system $\mathrm{KTS}(n)$. Such systems exist if and only if $n \equiv 3 \pmod 6$. The Kirkman schoolgirls problem, of finding a $\mathrm{KTS}(15)$, was one of the classical combinatorial problems, solved by T.P. Kirkman in 1850.

A Steiner triple system gives rise to a quasi-group structure on the underlying set, defined by the binary operation $x \cdot x = x$ and $x \cdot y = z$ when $x\ne y$ and $\{x,y,z\}$ is the unique block containing $\{x,y\}$.


References

  • Thomas Beth, Dieter Jungnickel, Hanfried Lenz, "Design theory", Cambridge University Press (1986) Zbl 0602.05001
  • Anne Penfold Street, Deborah J. Street, "Combinatorics of experimental design", Clarendon Press (1987) ISBN 0-19-853255-5 Zbl 0622.05001
How to Cite This Entry:
Steiner triple system. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Steiner_triple_system&oldid=54266