TOPICS
Search

Steiner Triple System


Let X be a set of v>=3 elements together with a set B of 3-subset (triples) of X such that every 2-subset of X occurs in exactly one triple of B. Then B is called a Steiner triple system and is a special case of a Steiner system with t=2 and k=3. A Steiner triple system S(v)=S(v,k=3,lambda=1) of order v exists iff v=1,3 (mod 6) (Kirkman 1847). In addition, if Steiner triple systems S_1 and S_2 of orders v_1 and v_2 exist, then so does a Steiner triple system S of order v_1v_2 (Ryser 1963, p. 101).

SteinerTripleSystemS9

Examples of Steiner triple systems S(v) of small orders v are

S_3={{1,2,3}}
(1)
S_7={{1,2,4},{2,3,5},{3,4,6},{4,5,7},{5,6,1},{6,7,2},{7,1,3}}
(2)
S_9={{1,2,3},{4,5,6},{7,8,9},{1,4,7},{2,5,8},{3,6,9},{1,5,9},{2,6,7},{3,4,8},{1,6,8},{2,4,9},{3,5,7}}.
(3)

The Steiner triple system S_9 is illustrated above.

The numbers of nonisomorphic Steiner triple systems S(v) of orders v=7, 9, 13, 15, 19, ... (i.e., 6k+1,3) are 1, 1, 2, 80, 11084874829, ... (Stinson and Ferch 1985; Colbourn and Dinitz 1996, pp. 14-15; Kaski and Östergård 2004; OEIS A030129). S(7) is the same as the finite projective plane of order 2. S(9) is a finite affine plane which can be constructed from the array

 a b c; d e f; g h i.
(4)

One of the two S(13)s is a finite hyperbolic plane. The 80 Steiner triple systems S(15) have been studied by Tonchev and Weishaar (1997).


See also

Hadamard Matrix, Kirkman Triple System, Social Golfer Problem, Steiner Quadruple System, Steiner System

Explore with Wolfram|Alpha

References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 107-109 and 274, 1987.Colbourn, C. J. and Dinitz, J. H. (Eds.). "Steiner Triple Systems." §4.5 in CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, pp. 14-15 and 70, 1996.Gardner, M. "Mathematical Games: On the Remarkable Császár Polyhedron and Its Applications in Problem Solving." Sci. Amer. 232, 102-107, May 1975.Kaski, P. and Östergård, P. R. J. "The Steiner Triple Systems of Order 19." Math. Comput. 73, 2075-2092, 2004.Kaski, P.; Östergård, P. R. J.; Topalova, S.; and Zlatarski, R. "Steiner Triple Systems of Order 19 and 21 with Subsystems of Order 7." http://www.tcs.hut.fi/~pkaski/19and21.ps.Kirkman, T. P. "On a Problem in Combinatorics." Cambridge Dublin Math. J. 2, 191-204, 1847.Lindner, C. C. and Rodger, C. A. Design Theory. Boca Raton, FL: CRC Press, 1997.Ryser, H. J. Combinatorial Mathematics. Buffalo, NY: Math. Assoc. Amer., pp. 99-102, 1963.Sloane, N. J. A. Sequence A030129 in "The On-Line Encyclopedia of Integer Sequences."Stinson, D. R. and Ferch, H. "2000000 Steiner Triple Systems of Order 19." Math. Comput. 44, 533-535, 1985.Tonchev, V. D. and Weishaar, R. S. "Steiner Triple Systems of Order 15 and Their Codes." J. Stat. Plan. Inference 58, 207-216, 1997.

Referenced on Wolfram|Alpha

Steiner Triple System

Cite this as:

Weisstein, Eric W. "Steiner Triple System." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SteinerTripleSystem.html

Subject classifications