Difference between revisions of "Steiner system"
m (links) |
m (link) |
||
Line 5: | Line 5: | ||
is an integer for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767019.png" /> satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767020.png" />. The sufficiency of this condition was proved for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767024.png" /> (see [[#References|[3]]], [[#References|[4]]]). | is an integer for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767019.png" /> satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767020.png" />. The sufficiency of this condition was proved for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767024.png" /> (see [[#References|[3]]], [[#References|[4]]]). | ||
− | In 1844 W. Woolhouse stated the existence problem for Steiner systems, and P. Kirkman solved it in 1847 for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767025.png" /> (Steiner triple | + | In 1844 W. Woolhouse stated the existence problem for Steiner systems, and P. Kirkman solved it in 1847 for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767025.png" /> ([[Steiner triple system]]s). In 1853 J. Steiner examined the case of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767026.png" />. |
Problems usually considered for Steiner systems are: 1) the determination of the maximum number of mutually non-isomorphic Steiner systems of a given order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767027.png" />; 2) the existence of Steiner systems with a given group of automorphisms; 3) the imbedding of partial Steiner systems (not containing some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767028.png" />-subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767029.png" />) in a finite Steiner system; 4) the existence of resolvable Steiner systems (with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767030.png" /> representable as a union of partitions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767031.png" />); 5) the maximal packing (minimal covering) of a complete set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767032.png" />-subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767033.png" /> by disjoint <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767034.png" /> (using Steiner systems). | Problems usually considered for Steiner systems are: 1) the determination of the maximum number of mutually non-isomorphic Steiner systems of a given order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767027.png" />; 2) the existence of Steiner systems with a given group of automorphisms; 3) the imbedding of partial Steiner systems (not containing some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767028.png" />-subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767029.png" />) in a finite Steiner system; 4) the existence of resolvable Steiner systems (with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767030.png" /> representable as a union of partitions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767031.png" />); 5) the maximal packing (minimal covering) of a complete set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767032.png" />-subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767033.png" /> by disjoint <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087670/s08767034.png" /> (using Steiner systems). |
Latest revision as of 15:16, 19 March 2018
A pair , where
is a finite set of
elements and
is a set of
-subsets in
(called blocks) such that every
-subset from
is contained in exactly one block of
. The number
is called the order of the Steiner system
. A Steiner system is a particular case of a block design and of a tactical configuration. A Steiner system for
is a balanced incomplete block design (BIBD), and for
,
it is a finite projective plane. A necessary condition for the existence of a Steiner system
is that the number
![]() |
is an integer for all satisfying
. The sufficiency of this condition was proved for
,
,
,
(see [3], [4]).
In 1844 W. Woolhouse stated the existence problem for Steiner systems, and P. Kirkman solved it in 1847 for (Steiner triple systems). In 1853 J. Steiner examined the case of
.
Problems usually considered for Steiner systems are: 1) the determination of the maximum number of mutually non-isomorphic Steiner systems of a given order ; 2) the existence of Steiner systems with a given group of automorphisms; 3) the imbedding of partial Steiner systems (not containing some
-subsets of
) in a finite Steiner system; 4) the existence of resolvable Steiner systems (with
representable as a union of partitions of
); 5) the maximal packing (minimal covering) of a complete set of
-subsets of
by disjoint
(using Steiner systems).
The majority of results on Steiner systems are obtained for small values of and
(see [2]–[4]).
References
[1] | J. Steiner, "Combinatorische Aufgaben" J. Reine Angew. Math. , 45 (1853) pp. 181–182 |
[2] | M. Hall, "Combinatorial theory" , Wiley (1986) |
[3] | C.C. Lindner, A. Rosa, "Steiner quadruple systems. A survey" Discrete Math. , 22 (1978) pp. 147–181 |
[4] | H. Hanani, "Balanced incomplete block designs and related designs" Discrete Math. , 11 (1975) pp. 255–369 |
Comments
The name "Steiner system" is somewhat inappropriate, since the systems studied by Steiner in [1] are not Steiner systems for
.
There is a rapidly growing literature on Steiner systems and related types of incidence structures, comprising thousands of papers. In what follows, only very few outstanding original papers are quoted; the reader is instead referred to the textbooks [2], [a1]–[a2], the collections of papers [a3]–[a5] and the surveys [a6]–[a8] for a detailed discussion and complete references. Regarding the existence of small systems, the reader should consult the tables [a9]–[a10].
The main problems usually studied are as follows.
Existence.
The only pairs for which the existence problem is completely settled are still those listed in the original article above. For
a very strong asymptotic existence result is due to R.M. Wilson [a11]–[a13]: For any fixed
, the necessary conditions
and
are sufficient for all but finitely many values of
. Unfortunately, the bounds on
extractable from Wilson's work are exceedingly large. Progress has been made for some small values of
; e.g., for
there are only 89 values of
left for which the existence of an
is undecided, the largest of which is
. Similar results hold for
. Considerably less is known for
. The outstanding problem of the existence of non-trivial Steiner systems with
is still open. For
, existence is known only for the seven pairs
,
,
,
,
,
, and
.
Enumeration.
Once existence is settled, one is interested in the number of isomorphism classes of Steiner systems
. The function
grows very rapidly with
(for fixed
); e.g.,
,
, but
. Wilson [a11]–[a13] proved
for all admissible
which are sufficiently large (where
is a constant depending on
). For
, one has
![]() |
The only known similar result for concerns
. For some small parameter triples, a complete enumeration is possible. E.g., the projective and affine planes are unique up to order 8, and so are the Witt designs
and
[a14].
Automorphism groups.
Much effort is spent in constructing Steiner systems with "nice" (usually this means large, at least point-transitive) automorphism groups. It appears that most Steiner systems are rigid (i.e., have no non-trivial automorphism), but this has only been demonstrated for (where it is known that the proportion of rigid Steiner triple systems
among all Steiner triple systems
approaches 1 as
). The particularly interesting existence problem for cyclic Steiner systems (those with a point-transitive cyclic group of automorphisms) has also been settled completely only for
; the case
is at present studied extensively.
Characterization and classification.
In view of the results on mentioned above, the complete classification of all
is only feasible for small values of the parameters. One therefore is interested in characterizing the "classical" series of examples (in particular, the Steiner systems
and
formed by the points and lines in the
-dimensional affine, respectively projective, space over
and the Hermitian unitals formed by the absolute points and the non-absolute lines of a unitary polarity of
) and in classifying Steiner systems with interesting automorphism groups. E.g., all systems
with a group which is
-homogeneous on points have been classified; except for the three classical series just mentioned, there are only two further series and a few sporadic examples. At present one works on the classification of systems
with a flag-transitive or a point-primitive group.
Resolvable Steiner systems.
Here is a union of parallel classes (i.e., partitions of the point set
). A resolvable
is usually denoted by
and also called a Kirkman system (since the seminal case of an
is equivalent to a solution of Kirkman's famous schoolgirl problem posed in 1850). One clearly has the further necessary condition
for the existence of an
. For
, the necessary condition
is known to be sufficient for
and
; it is also asymptotically sufficient for any fixed
. The cases
and
are almost settled (with about 100 undecided values of
in either case). Much less is known for
; only the case
is almost settled.
Subsystems.
Another problem of interest is the existence of an with a subsystem
. Up till now (1990) this has only been considered for
. Here one obtains the additional necessary condition
, which is known to be sufficient for
and
. Similarly, an
with a sub-
exists if and only if
and
.
Imbeddings.
One question concerns the possibility of imbedding a "partial" in some
. E.g., a partial
can be imbedded in an
for all values of
with
and
or
. Another question which has been studied in many special instances concerns imbeddings of partial
's in finite projective planes. Here the outstanding problem is the conjecture that any partial
can be imbedded in a finite projective plane (possibly even in a Desarguesian plane
).
Large sets of Steiner systems and packings.
A large set is a partition of the set of all -subsets of a
-set into Steiner systems
. The outstanding result here is the existence of a large set of
for all
or
(with 6 possible exceptions) proved by Lu Jia-Xi in a series of papers [a15]. One also knows the existence of a large set of
's. More generally, one is interested in (bounds on) the maximum number
of pairwise disjoint
's (i.e. packings of
's).
Generalizations.
Steiner systems have been generalized in many ways, and problems analogous to the ones discussed here are studied for these generalizations. The most obvious generalization is that to 's, where one requires that any
-set of points is contained in exactly
common blocks. An
is called simple if there are no two blocks which are incident with the same set of points. L. Teirlinck [a16] proved that there exist non-trivial simple
's for every
, thus settling an outstanding problem. Another generalization is allowance of different block sizes; this has been mainly studied for the case
; the resulting structures are called pairwise balanced designs and are a fundamental tool for the existence theory of Steiner systems with
. One also considers packing and covering of all
-subsets of a
-set by
-subsets. Finally, sets of mutually orthogonal Latin squares can be considered as a generalization of affine planes, i.e. of systems
.
Connections to other areas.
Finally, the study of Steiner systems and their generalizations is closely connected to several other areas of mathematics, such as geometry, group theory and coding theory. The best-known example is provided by the Witt designs mentioned above, which are essentially equivalent to the Mathieu groups and the Golay codes, see [a1], [a17], [a18]. On the other hand, there are also important applications of combinatorial designs in general, and Steiner systems in particular, e.g. in computer science and cryptography [a19].
References
[a1] | T. Beth, D. Jungnickel, H. Lenz, "Design theory" , Cambridge Univ. Press (1986) |
[a2] | D.R. Hughes, F.C. Piper, "Design theory" , Cambridge Univ. Press (1985) |
[a3] | C.C. Lindner (ed.) A. Rosa (ed.) , Topics on Steiner systems , North-Holland (1980) |
[a4] | C.J. Colbourn (ed.) R.A. Mathon (ed.) , Combinatorial design theory , North-Holland (1987) |
[a5] | A. Hartman (ed.) , Combinatorial designs , North-Holland (1989) |
[a6] | J. Doyen, A. Rosa, "An extended bibliography and survey of Steiner systems" Congressus Numerantium , 20 (1978) pp. 297–361 |
[a7] | J. Doyen, A. Rosa, "An extended bibliography of Steiner systems" Ann. Discr. Math. , 7 (1980) pp. 317–349 |
[a8] | D. Jungnickel, "Design theory: an update" Ars Comb. , 28 (1989) pp. 129–199 |
[a9] | R.A. Mathon, A. Rosa, "Tables of parameters of BIBD's with ![]() |
[a10] | Y.M. Chee, C.J. Colbourn, D.L. Kreher, "Simple ![]() ![]() |
[a11] | R.M. Wilson, "An existence theory for pairwise balanced designs I" J. Comb. Th. (A) , 13 (1972) pp. 220–245 |
[a12] | R.M. Wilson, "An existence theory for pairwise balanced designs II" J. Comb. Th. (A) , 13 (1972) pp. 246–273 |
[a13] | R.M. Wilson, "An existence theory for pairwise balanced designs III" J. Comb. Th. (A) , 18 (1975) pp. 71–79 |
[a14] | E. Witt, "Über Steinersche Systeme" Abh. Math. Sem. Hamburg , 12 (1938) pp. 265–275 |
[a15] | Jia-Xi Lu, "On large sets of disjoint Steiner triple systems, VI" J. Comb. Th. (A) , 37 (1984) pp. 189–192 |
[a16] | L. Teirlinck, "Non-trivial ![]() ![]() |
[a17] | F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes" , I-II , North-Holland (1978) |
[a18] | H. Lüneburg, "Transitive Erweiterungen endlicher Permutationsgruppen" , Lect. notes in math. , 84 , Springer (1969) |
[a19] | C.J. Colbourn, P.C. van Oorschot, "Applications of combinatorial designs in computer science" ACM Comp. Surveys , 21 (1989) pp. 223–250 |
Steiner system. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Steiner_system&oldid=42977