Steiner system
In combinatorial mathematics, a Steiner system is a type of block design, specifically a t-design with λ = 1 and t = 2 or t ≥ 2.
A Steiner system with parameters t, k, n, written S, is an n-element set S together with a set of k-element subsets of S with the property that each t-element subset of S is contained in exactly one block. In an alternative notation for block designs, an S would be a t- design.
This definition is relatively new. The classical definition of Steiner systems also required that k = t + 1. An S was called a Steiner triple ''system, while an S is called a Steiner quadruple system, and so on. With the generalization of the definition, this naming system is no longer strictly adhered to.
Long-standing problems in design theory were whether there exist any nontrivial Steiner systems with t'' ≥ 6; also whether infinitely many have t = 4 or 5. Both existences were proved by Peter Keevash in 2014. His proof is non-constructive and, as of 2019, no actual Steiner systems are known for large values of t.
Types of Steiner systems
A finite projective plane of order, with the lines as blocks, is an, since it has points, each line passes through points, and each pair of distinct points lies on exactly one line.A finite affine plane of order, with the lines as blocks, is an. An affine plane of order can be obtained from a projective plane of the same order by removing one block and all of the points in that block from the projective plane. Choosing different blocks to remove in this way can lead to non-isomorphic affine planes.
An S is called a Steiner quadruple system. A necessary and sufficient condition for the existence of an S is that n 2 or 4. The abbreviation SQS is often used for these systems. Up to isomorphism, SQS and SQS are unique, there are 4 SQSs and 1,054,163 SQSs.
An S is called a Steiner quintuple system. A necessary condition for the existence of such a system is that n 3 or 5 which comes from considerations that apply to all the classical Steiner systems. An additional necessary condition is that n 4, which comes from the fact that the number of blocks must be an integer. Sufficient conditions are not known. There is a unique Steiner quintuple system of order 11, but none of order 15 or order 17. Systems are known for orders 23, 35, 47, 71, 83, 107, 131, 167 and 243. The smallest order for which the existence is not known is 21.
Steiner triple systems
An S is called a Steiner triple system, and its blocks are called triples. It is common to see the abbreviation STS for a Steiner triple system of order n. The total number of pairs is n/2, of which three appear in a triple, and so the total number of triples is n/6. This shows that n must be of the form 6k+1 or 6k + 3 for some k. The fact that this condition on n is sufficient for the existence of an S was proved by Raj Chandra Bose and T. Skolem. The projective plane of order 2 is an STS and the affine plane of order 3 is an STS. Up to isomorphism, the STS and STS are unique, there are two STSs, 80 STSs, and 11,084,874,829 STSs.We can define a multiplication on the set S using the Steiner triple system by setting aa = a for all a in S, and ab = c if is a triple. This makes S an idempotent, commutative quasigroup. It has the additional property that ab = c implies bc = a and ca = b. Conversely, any quasigroup with these properties arises from a Steiner triple system. Commutative idempotent quasigroups satisfying this additional property are called Steiner quasigroups.
Resolvable Steiner systems
Some of the S systems can have their triples partitioned into /2 sets each having pairwise disjoint triples. This is called resolvable and such systems are called Kirkman triple systems after Thomas Kirkman, who studied such resolvable systems before Steiner. Dale Mesner, Earl Kramer, and others investigated collections of Steiner triple systems that are mutually disjoint. It is known that seven different S systems can be generated to together cover all 84 triplets on a 9-set; it was also known by them that there are 15360 different ways to find such 7-sets of solutions, which reduce to two non-isomorphic solutions under relabeling, with multiplicities 6720 and 8640 respectively.The corresponding question for finding thirteen different disjoint S systems was asked by James Sylvester in 1860 as an extension of the Kirkman's schoolgirl problem, namely whether Kirkman's schoolgirls could march for an entire term of 13 weeks with no triplet of girls being repeated over the whole term. The question was solved by RHF Denniston in 1974, who constructed Week 1 as follows:
Day 1 ABJ CEM FKL HIN DGO
Day 2 ACH DEI FGM JLN BKO
Day 3 ADL BHM GIK CFN EJO
Day 4 AEG BIL CJK DMN FHO
Day 5 AFI BCD GHJ EKN LMO
Day 6 AKM DFJ EHL BGN CIO
Day 7 BEF CGL DHK IJM ANO
for girls labeled A to O, and constructed each subsequent week's solution from its immediate predecessor by changing A to B, B to C,... L to M and M back to A, all while leaving N and O unchanged. The Week 13 solution, upon undergoing that relabeling, returns to the Week 1 solution. Denniston reported in his paper that the search he employed took 7 hours on an Elliott 4130 computer at the University of Leicester, and he immediately ended the search on finding the solution above, not looking to establish uniqueness. The number of non-isomorphic solutions to Sylvester's problem remains unknown as of 2021.
Properties
It is clear from the definition of that.If exists, then taking all blocks containing a specific element and discarding that element gives a derived system. Therefore, the existence of is a necessary condition for the existence of.
The number of -element subsets in is, while the number of -element subsets in each block is. Since every -element subset is contained in exactly one block, we have, or
where is the number of blocks. Similar reasoning about -element subsets containing a particular element gives us, or
where is the number of blocks containing any given element. From these definitions follows the equation. It is a necessary condition for the existence of that and are integers. As with any block design, Fisher's inequality is true in Steiner systems.
Given the parameters of a Steiner system and a subset of size, contained in at least one block, one can compute the number of blocks intersecting that subset in a fixed number of elements by constructing a Pascal triangle. In particular, the number of blocks intersecting a fixed block in any number of elements is independent of the chosen block.
The number of blocks that contain any i-element set of points is:
It can be shown that if there is a Steiner system, where is a prime power greater than 1, then 1 or. In particular, a Steiner triple system must have. And as we have already mentioned, this is the only restriction on Steiner triple systems, that is, for each natural number, systems and exist.
History
Steiner triple systems were defined for the first time by Wesley S. B. Woolhouse in 1844 in the Prize question #1733 of Lady's and Gentlemen's Diary. The posed problem was solved by. In 1850 Kirkman posed a variation of the problem known as Kirkman's schoolgirl problem, which asks for triple systems having an additional property. Unaware of Kirkman's work, reintroduced triple systems, and as this work was more widely known, the systems were named in his honor.In 1910 Geoffrey Thomas Bennett gave a graphical representation for Steiner triple systems.
Mathieu groups
Several examples of Steiner systems are closely related to group theory. In particular, the finite simple groups called Mathieu groups arise as automorphism groups of Steiner systems:- The Mathieu group M11 is the automorphism group of a S Steiner system
- The Mathieu group M12 is the automorphism group of a S Steiner system
- The Mathieu group M22 is the unique index 2 subgroup of the automorphism group of a S Steiner system
- The Mathieu group M23 is the automorphism group of a S Steiner system
- The Mathieu group M24 is the automorphism group of a S Steiner system.
The Steiner system S(5, 6, 12)
Projective line construction
This construction is due to Carmichael.Add a new element, call it, to the 11 elements of the finite field 11. This set,, of 12 elements can be formally identified with the points of the projective line over 11. Call the following specific subset of size 6,
a "block". From this block, we obtain the other blocks of the S system by repeatedly applying the linear fractional transformations:
where are in 11 and.
With the usual conventions of defining and, these functions map the set onto itself. In geometric language, they are projectivities of the projective line. They form a group under composition which is the projective special linear group PSL of order 660. There are exactly five elements of this group that leave the starting block fixed setwise, namely those such that and so that. So there will be 660/5 = 132 images of that block. As a consequence of the multiply transitive property of this group acting on this set, any subset of five elements of will appear in exactly one of these 132 images of size six.