Editing Steiner system (section)

== Types of Steiner systems==

A '''finite [[projective plane]]''' of order {{math|''q''}}, with the lines as blocks, is an {{math|S(2, ''q'' + 1, ''q''<sup>2</sup> + ''q'' + 1)}}, since it has {{math|''q''<sup>2</sup> + ''q'' + 1}} points, each line passes through {{math|''q'' + 1}} points, and each pair of distinct points lies on exactly one line.

A '''finite [[Affine plane (incidence geometry)|affine plane]]''' of order {{math|''q''}}, with the lines as blocks, is an {{math|S(2,&nbsp;''q'',&nbsp;''q''<sup>2</sup>)}}. An affine plane of order {{math|''q''}} 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(3,4,''n'') is called a '''Steiner quadruple system'''. A necessary and sufficient condition for the existence of an S(3,4,''n'') is that ''n'' <math>\equiv</math> 2 or 4 (mod 6). The abbreviation SQS(''n'') is often used for these systems. Up to isomorphism, SQS(8) and SQS(10) are unique, there are 4 SQS(14)s and 1,054,163 SQS(16)s.<ref>{{harvnb|Colbourn|Dinitz|2007|loc=pg.106}}</ref>

An S(4,5,''n'') is called a '''Steiner quintuple system'''. A necessary condition for the existence of such a system is that ''n'' <math>\equiv</math> 3 or 5 (mod 6) which comes from considerations that apply to all the classical Steiner systems. An additional necessary condition is that ''n'' <math>\not\equiv</math> 4 (mod 5), 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.<ref>{{harvnb|Östergard|Pottonen|2008}}</ref> 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 (as of 2011) is 21.

===Steiner triple systems===
An S(2,3,''n'') is called a '''Steiner triple system''', and its blocks are called '''triples'''. It is common to see the abbreviation STS(''n'') for a Steiner triple system of order ''n''. The total number of pairs is ''n(n-1)/2'', of which three appear in a triple, and so the total number of triples is ''n''(''n''&minus;1)/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(2,3,''n'') was proved by [[Raj Chandra Bose]]<ref>{{Cite journal | doi=10.1111/j.1469-1809.1939.tb02219.x|title = On the Construction of Balanced Incomplete Block Designs| journal=Annals of Eugenics| volume=9| issue=4| pages=353–399|year = 1939|last1 = Bose|first1 = R. C.| doi-access=free}}</ref> and T. Skolem.<ref>T. Skolem. [http://www.mscand.dk/article/view/10551 Some remarks on the triple systems of Steiner.] Math. Scand. 6 (1958), 273–280.</ref> The projective plane of order 2 (the [[Fano plane]]) is an STS(7) and the [[Affine plane (incidence geometry)|affine plane]] of order 3 is an STS(9). Up to isomorphism, the STS(7) and STS(9) are unique, there are two STS(13)s, 80 STS(15)s, and 11,084,874,829 STS(19)s.<ref name=Handbook>{{harvnb|Colbourn|Dinitz|2007|loc=pg.60}}</ref>

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 {''a'',''b'',''c''} is a triple. This makes ''S''  an [[idempotent]], [[commutative]] [[quasigroup]].  It has the additional property that ''ab'' = ''c'' implies ''bc'' = ''a'' and ''ca'' = ''b''.{{NoteTag|This property is equivalent to saying that (xy)y {{=}} x for all x and y in the idempotent commutative quasigroup.}}  Conversely, any (finite) quasigroup with these properties arises from a Steiner triple system. Commutative idempotent quasigroups satisfying this additional property are called ''Steiner quasigroups''.<ref>{{harvnb|Colbourn|Dinitz|2007|loc=pg. 497, definition 28.12}}</ref>

===Resolvable Steiner systems===
Some of the S(2,3,n) systems can have their triples partitioned into (n-1)/2 sets each having (n/3) 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 (i.e., no two Steiner systems in such a collection share a common triplet). It is known (Bays 1917, Kramer & Mesner 1974) that seven different S(2,3,9) 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(2,3,15) systems was asked by [[James Joseph Sylvester|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,<ref name="denniston">{{cite journal| title = Denniston's paper, open access| journal = Discrete Mathematics| date = September 1974| volume = 9| issue = 3| pages = 229–233| doi = 10.1016/0012-365X(74)90004-1| last1 = Denniston| first1 = R. H. F.| doi-access = free}}</ref> who constructed Week 1 as follows:

<pre>
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
</pre>

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 Brothers (computer company)|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.