Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Steiner system
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|Block design in combinatorial mathematics}} [[image:Fano plane.svg|250px|right|thumbnail|The [[Fano plane]] is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line.]] In [[Combinatorics|combinatorial]] [[mathematics]], a '''Steiner system''' (named after [[Jakob Steiner]]) is a type of [[block design]], specifically a [[Block design#Generalization: t-designs|t-design]] with λ = 1 and ''t'' = 2 or (recently) ''t'' ≥ 2. A Steiner system with parameters ''t'', ''k'', ''n'', written S(''t'',''k'',''n''), is an ''n''-element [[Set (mathematics)|set]] ''S'' together with a set of ''k''-element [[subset]]s of ''S'' (called '''blocks''') 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(''t'',''k'',''n'') would be a ''t''-(''n'',''k'',1) design. This definition is relatively new. The classical definition of Steiner systems also required that ''k'' = ''t'' + 1. An S(2,3,''n'') was (and still is) called a ''Steiner triple'' (or ''triad'') ''system'', while an S(3,4,''n'') 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 [[block design|design theory]] were whether there exist any nontrivial Steiner systems (nontrivial meaning ''t'' < ''k'' < ''n'') with ''t'' ≥ 6; also whether infinitely many have ''t'' = 4 or 5.<ref>{{cite web|url=http://designtheory.org/library/encyc/tdes/g |title=Encyclopaedia of Design Theory: t-Designs |publisher=Designtheory.org |date=2004-10-04 |access-date=2012-08-17}}</ref> 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''.<ref>{{cite arXiv |last=Keevash |first=Peter |eprint=1401.3665 |title=The existence of designs |date=2014|class=math.CO }}</ref><ref>{{cite web|author=Erica Kleirrach|url=https://www.quantamagazine.org/150-year-old-math-design-problem-solved-20150609/ |title=A Design Dilemma Solved, Minus Designs |publisher=Quanta Magazine |date=2015-06-09 |access-date=2015-06-27}}</ref><ref>{{cite web|last1=Kalai|first1=Gil|title=Designs exist!|url=http://www.bourbaki.ens.fr/TEXTES/1100.pdf|publisher=Séminaire Bourbaki}}</ref> == 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, ''q'', ''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''−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. == Properties == It is clear [[logical consequence|from the definition]] of {{math|S(''t'', ''k'', ''n'')}} that <math>1 < t < k < n</math>. (Equalities, while technically possible, lead to trivial systems.) If {{math|S(''t'', ''k'', ''n'')}} exists, then taking all blocks containing a specific element and discarding that element gives a ''derived system'' {{math|S(''t''−1, ''k''−1, ''n''−1)}}. Therefore, the existence of {{math|S(''t''−1, ''k''−1, ''n''−1)}} is a necessary condition for the existence of {{math|S(''t'', ''k'', ''n'')}}. The number of {{math|''t''}}-element subsets in {{math|S}} is <math>\tbinom n t</math>, while the number of {{math|''t''}}-element subsets in each block is <math>\tbinom k t</math>. Since every {{math|''t''}}-element subset is contained in exactly one block, we have <math>\tbinom n t = b\tbinom k t</math>, or :<math>b = \frac{\tbinom nt}{\tbinom kt} = \frac{n(n-1)\cdots(n-t+1)}{k(k-1)\cdots(k-t+1)},</math> where {{math|''b''}} is the number of blocks. Similar reasoning about {{math|''t''}}-element subsets containing a particular element gives us <math>\tbinom{n-1}{t-1}=r\tbinom{k-1}{t-1}</math>, or :<math>r=\frac{\tbinom{n-1}{t-1}}{\tbinom{k-1}{t-1}}</math> =<math>\frac{(n-t+1)\cdots(n-2)(n-1)}{(k-t+1)\cdots(k-2)(k-1)},</math> where {{math|''r''}} is the number of blocks containing any given element. From these definitions follows the equation <math>bk=rn</math>. It is a necessary condition for the existence of {{math|S(''t'', ''k'', ''n'')}} that {{math|''b''}} and {{math|''r''}} are integers. As with any block design, [[Fisher's inequality]] <math>b\ge n</math> is true in Steiner systems. Given the parameters of a Steiner system {{math|S(''t, k, n'')}} and a subset of size <math>t' \leq t</math>, 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]].{{sfn|Assmus|Key|1992|page=8}} 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: :<math> \lambda_i = \left.\binom{n-i}{t-i} \right/ \binom{k-i}{t-i} \text{ for } i = 0,1,\ldots,t, </math> It can be shown that if there is a Steiner system {{math|S(2, ''k'', ''n'')}}, where {{math|''k''}} is a [[prime power]] greater than 1, then {{math|''n''}} <math>\equiv</math> 1 or {{math|''k'' (mod ''k''(''k''−1))}}. In particular, a Steiner triple system {{math|S(2, 3, ''n'')}} must have {{math|1=''n'' = 6''m'' + 1 or 6''m'' + 3}}. And as we have already mentioned, this is the only restriction on Steiner triple systems, that is, for each [[natural number]] {{math|''m''}}, systems {{math|S(2, 3, 6''m'' + 1)}} and {{math|S(2, 3, 6''m'' + 3)}} 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.<ref>{{harvnb|Lindner|Rodger|1997|loc=pg.3}}</ref> The posed problem was solved by {{Harvs|first=Thomas|last=Kirkman|authorlink=Thomas Kirkman|year=1847|txt}}. In 1850 Kirkman posed a variation of the problem known as [[Kirkman's schoolgirl problem]], which asks for triple systems having an additional property (resolvability). Unaware of Kirkman's work, {{harvs|first=Jakob|last=Steiner|authorlink=Jakob Steiner|year=1853|txt}} 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.<ref>{{cite journal|author=Baker, H. F.|author-link=H. F. Baker|title=Obituary. Dr. G. T. Bennett, F.R.S.|journal=Nature|date=November 13, 1943|volume=152|issue=3863|pages=558–559|doi=10.1038/152558a0}}</ref><ref>{{cite journal|author=Bennett, G. T.|title=The Double Six|journal=Proceedings of the London Mathematical Society|volume=2|issue=1|year=1911|pages=336-351|url=https://ia600708.us.archive.org/view_archive.php?archive=/28/items/crossref-pre-1923-scholarly-works/10.1112%252Fplms%252Fs2-10.1.116.zip&file=10.1112%252Fplms%252Fs2-9.1.336.pdf}}</ref><ref>{{cite journal|author=Bennett, G. T.|title=The System of Lines of a Cubic Surface|journal=Proceedings of the London Mathematical Society|volume=2|issue=1|year=1912|pages=479-484|url=https://ia800708.us.archive.org/view_archive.php?archive=/28/items/crossref-pre-1923-scholarly-works/10.1112%252Fplms%252Fs2-10.1.116.zip&file=10.1112%252Fplms%252Fs2-10.1.479.pdf}}</ref> == Mathieu groups == Several examples of Steiner systems are closely related to [[group theory]]. In particular, the [[List of finite simple groups|finite simple groups]] called [[Mathieu group]]s arise as [[automorphism group]]s of Steiner systems: * The [[Mathieu group M11|Mathieu group M<sub>11</sub>]] is the automorphism group of a S(4,5,11) Steiner system * The [[Mathieu group M12|Mathieu group M<sub>12</sub>]] is the automorphism group of a S(5,6,12) Steiner system * The [[Mathieu group M22|Mathieu group M<sub>22</sub>]] is the unique index 2 subgroup of the automorphism group of a S(3,6,22) Steiner system * The [[Mathieu group M23|Mathieu group M<sub>23</sub>]] is the automorphism group of a S(4,7,23) Steiner system * The [[Mathieu group M24|Mathieu group M<sub>24</sub>]] is the automorphism group of a S(5,8,24) Steiner system. == The Steiner system S(5, 6, 12) == There is a unique S(5,6,12) Steiner system; its automorphism group is the [[Mathieu group]] M<sub>12</sub>, and in that context it is denoted by W<sub>12</sub>. === Projective line construction === This construction is due to Carmichael (1937).<ref>{{harvnb|Carmichael|1956|page=431}}</ref> Add a new element, call it {{mvar|∞}}, to the 11 elements of the [[finite field]] {{mvar|'''F'''}}<sub>11</sub> (that is, the integers mod 11). This set, {{mvar|''S''}}, of 12 elements can be formally identified with the points of the [[projective line]] over {{mvar|'''F'''}}<sub>11</sub>. Call the following specific subset of size 6, :<math>\{\infty,1,3,4,5,9\}, </math> a "block" (it contains {{math|∞}} together with the 5 nonzero squares in {{mvar|'''F'''}}<sub>11</sub>). From this block, we obtain the other blocks of the {{mvar|S}}(5,6,12) system by repeatedly applying the [[linear fractional transformation]]s: :<math>z' = f(z) = \frac{az + b}{cz + d},</math> where {{mvar|a,b,c,d}} are in {{mvar|'''F'''}}<sub>11</sub> and {{math|1= ''ad − bc'' = 1}}. With the usual conventions of defining {{math|1= ''f'' (−''d''/''c'') = ∞}} and {{math|1= ''f'' (∞) = ''a''/''c''}}, these functions map the set {{mvar|''S''}} onto itself. In geometric language, they are [[Projectivity|projectivities]] of the projective line. They form a [[group (mathematics)|group]] under composition which is the [[projective special linear group]] {{mvar|PSL}}(2,11) of order 660. There are exactly five elements of this group that leave the starting block fixed setwise,<ref>{{harvnb|Beth|Jungnickel|Lenz|1986|page=196}}</ref> namely those such that {{math|1= ''b=c=0''}} and {{math|1= ''ad''=1}} so that {{math|1= ''f(z) = a''<sup>2</sup> ''z''}}. So there will be 660/5 = 132 images of that block. As a consequence of the multiply transitive property of this group [[Group action (mathematics)|acting]] on this set, any subset of five elements of {{mvar|''S''}} will appear in exactly one of these 132 images of size six. === Kitten construction === An alternative construction of W<sub>12</sub> is obtained by use of the 'kitten' of R.T. Curtis,<ref>{{Harvnb|Curtis|1984}}</ref> which was intended as a "hand calculator" to write down blocks one at a time. The kitten method is based on completing patterns in a 3x3 grid of numbers, which represent an [[affine geometry]] on the [[vector space]] F<sub>3</sub>xF<sub>3</sub>, an S(2,3,9) system. === Construction from K<sub>6</sub> graph factorization === The relations between the [[graph factorization|graph factors]] of the [[complete graph|complete graph K<sub>6</sub>]] generate an S(5,6,12).<ref>{{cite web| url = http://linear.ups.edu/eagts/section-24.html| title = EAGTS textbook}}</ref> A K<sub>6</sub> graph has 6 vertices, 15 edges, 15 [[perfect matching]]s, and 6 different 1-factorizations (ways to partition the edges into disjoint perfect matchings). The set of vertices (labeled 123456) and the set of factorizations (labeled ''ABCDEF'') provide one block each. Every pair of factorizations has exactly one perfect matching in common. Suppose factorizations ''A'' and ''B'' have the common matching with edges 12, 34 and 56. Add three new blocks ''AB''3456, 12''AB''56, and 1234''AB'', replacing each edge in the common matching with the factorization labels in turn. Similarly add three more blocks 12''CDEF'', 34''CDEF'', and 56''CDEF'', replacing the factorization labels by the corresponding edge labels of the common matching. Do this for all 15 pairs of factorizations to add 90 new blocks. Finally, take the full set of <math>\tbinom{12}{6} = 924 </math> combinations of 6 objects out of 12, and discard any combination that has 5 or more objects in common with any of the 92 blocks generated so far. Exactly 40 blocks remain, resulting in {{nowrap|1=2 + 90 + 40 = 132}} blocks of the S(5,6,12). This method works because there is an [[automorphisms of the symmetric and alternating groups#The exceptional outer automorphism of S6|outer automorphism on the symmetric group ''S''<sub>6</sub>]], which maps the vertices to factorizations and the edges to partitions. Permuting the vertices causes the factorizations to permute differently, in accordance with the outer automorphism. == The Steiner system S(5, 8, 24) == The Steiner system S(5, 8, 24), also known as the '''Witt design''' or '''Witt geometry''', was first described by {{Harvs|txt|authorlink=Robert Daniel Carmichael|last=Carmichael|year=1931}} and rediscovered by {{Harvs|txt|last=Witt|year=1938|authorlink=Ernst Witt}}. This system is connected with many of the [[sporadic simple group]]s and with the [[exceptional object|exceptional]] 24-dimensional [[lattice (group)|lattice]] known as the [[Leech lattice]]. The automorphism group of S(5, 8, 24) is the [[Mathieu group M24|Mathieu group M<sub>24</sub>]], and in that context the design is denoted W<sub>24</sub> ("W" for "Witt") === Direct lexicographic generation === All 8-element subsets of a 24-element set are generated in [[lexicographic order]], and any such subset which differs from some subset already found in fewer than four positions is discarded. The list of octads for the elements 01, 02, 03, ..., 22, 23, 24 is then: :: 01 02 03 04 05 06 07 08 :: 01 02 03 04 09 10 11 12 :: 01 02 03 04 13 14 15 16 :: . :: . (next 753 octads omitted) :: . :: 13 14 15 16 17 18 19 20 :: 13 14 15 16 21 22 23 24 :: 17 18 19 20 21 22 23 24 Each single element occurs 253 times somewhere in some octad. Each pair occurs 77 times. Each triple occurs 21 times. Each quadruple (tetrad) occurs 5 times. Each quintuple (pentad) occurs once. Not every hexad, heptad or octad occurs. === Construction from the binary Golay code === The 4096 codewords of the 24-bit [[binary Golay code]] are generated, and the 759 codewords with a [[Hamming weight]] of 8 correspond to the S(5,8,24) system. The Golay code can be constructed by many methods, such as generating all 24-bit binary strings in lexicographic order and discarding those that [[Hamming distance|differ from some earlier one in fewer than 8 positions]]. The result looks like this: <pre> 000000000000000000000000 000000000000000011111111 000000000000111100001111 . . (next 4090 24-bit strings omitted) . 111111111111000011110000 111111111111111100000000 111111111111111111111111 </pre> The codewords form a [[group (mathematics)|group]] under the [[XOR]] operation. === Projective line construction === This construction is due to Carmichael (1931).<ref>{{harvnb|Carmichael|1931}}</ref> Add a new element, call it {{mvar|∞}}, to the 23 elements of the [[finite field]] {{mvar|'''F'''}}<sub>23</sub> (that is, the integers mod 23). This set, {{mvar|''S''}}, of 24 elements can be formally identified with the points of the [[projective line]] over {{mvar|'''F'''}}<sub>23</sub>. Call the following specific subset of size 8, :<math>\{\infty,0,1,3,12,15,21,22\}, </math> a "block". (We can take any octad of the extended [[binary Golay code]], seen as a quadratic residue code.) From this block, we obtain the other blocks of the {{mvar|S}}(5,8,24) system by repeatedly applying the [[linear fractional transformation]]s: :<math>z' = f(z) = \frac{az + b}{cz + d},</math> where {{mvar|a,b,c,d}} are in {{mvar|'''F'''}}<sub>23</sub> and {{math|1= ''ad − bc'' = 1}}. With the usual conventions of defining {{math|1= ''f'' (−''d''/''c'') = ∞}} and {{math|1= ''f'' (∞) = ''a''/''c''}}, these functions map the set {{mvar|''S''}} onto itself. In geometric language, they are [[Projectivity|projectivities]] of the projective line. They form a [[group (mathematics)|group]] under composition which is the [[projective special linear group]] {{mvar|PSL}}(2,23) of order 6072. There are exactly 8 elements of this group that leave the initial block fixed setwise. So there will be 6072/8 = 759 images of that block. These form the octads of S(5,8,24). === Construction from the [[Miracle Octad Generator]] === The [[Miracle Octad Generator]] (MOG) is a tool to generate octads, such as those containing specified subsets. It consists of a 4x6 array with certain weights assigned to the rows. In particular, an 8-subset should obey three rules in order to be an octad of S(5,8,24). First, each of the 6 columns should have the same [[Parity (mathematics)|parity]], that is, they should all have an odd number of cells or they should all have an even number of cells. Second, the top row should have the same parity as each of the columns. Third, the rows are respectively multiplied by the weights 0, 1, 2, and 3 over the [[Finite field#Field with four elements|finite field of order 4]], and column sums are calculated for the 6 columns, with multiplication and addition using the [[finite field arithmetic]] definitions. The resulting column sums should form a valid ''[[hexacode]]word'' of the form {{nowrap|(''a'', ''b'', ''c'', ''a'' + ''b'' + ''c'', ''3a'' + ''2b'' + ''c'', ''2a'' + ''3b'' + ''c'')}} where ''a, b, c'' are also from the finite field of order 4. If the column sums' parities don't match the row sum parity, or each other, or if there do not exist ''a, b, c'' such that the column sums form a valid hexacodeword, then that subset of 8 is not an octad of S(5,8,24). The MOG is based on creating a [[bijection]] (Conwell 1910, "The three-space PG(3,2) and its group") between the 35 ways to partition an 8-set into two different 4-sets, and the 35 lines of the [[Fano plane#Fano three-space|Fano 3-space]] PG(3,2). It is also geometrically related (Cullinane, "Symmetry Invariance in a Diamond Ring", Notices of the AMS, pp A193-194, Feb 1979) to the 35 different ways to partition a 4x4 array into 4 different groups of 4 cells each, such that if the 4x4 array represents a four-dimensional finite [[affine space]], then the groups form a set of parallel subspaces. == See also == * [[Constant weight code]] * [[Kirkman's schoolgirl problem]] * [[Sylvester–Gallai configuration]] == Notes == {{NoteFoot}} ==References== {{Reflist}} ==References== * {{citation|last1=Assmus|first1=E. F.|last2=Key|first2=J. D.|author2-link=Jennifer Key|title=Designs and Their Codes|publisher=Cambridge University Press|year=1992|place=Cambridge|isbn=978-0-521-41361-9}} * {{citation|first1=Thomas|last1=Beth|first2=Dieter|last2=Jungnickel|author-link2=Dieter Jungnickel|first3=Hanfried|last3=Lenz|author-link3=Hanfried Lenz|title=Design Theory|publisher=[[Cambridge University Press]]|location=Cambridge|year=1986}}. 2nd ed. (1999) {{isbn|978-0-521-44432-3}}. * {{citation|last=Carmichael|first=Robert|author-link=Robert Daniel Carmichael|title=Tactical Configurations of Rank Two|journal=American Journal of Mathematics|volume=53|issue=1|pages=217–240|year=1931|jstor=2370885|doi=10.2307/2370885}} * {{citation|last=Carmichael|first=Robert D.|author-link=Robert Daniel Carmichael|title=Introduction to the theory of Groups of Finite Order|year=1956|orig-year=1937|publisher=Dover|isbn=978-0-486-60300-1}} * {{citation | last1=Colbourn | first1=Charles J. | last2=Dinitz | first2=Jeffrey H. | title=Handbook of Combinatorial Designs | publisher=Chapman & Hall/ CRC | location=Boca Raton | zbl=0836.00010 | year=1996 | isbn=978-0-8493-8948-1 | url-access=registration | url=https://archive.org/details/crchandbookofcom0000unse }} * {{citation | last1=Colbourn | first1=Charles J. | last2=Dinitz | first2=Jeffrey H. | title=Handbook of Combinatorial Designs | year=2007 | publisher=Chapman & Hall/ CRC | location=Boca Raton | isbn=978-1-58488-506-1 | edition=2nd | zbl=1101.05001 | url-access=registration | url=https://archive.org/details/handbookofcombin0000unse }} * {{citation | last=Curtis|first=R.T.|contribution=The Steiner system S(5,6,12), the Mathieu group M<sub>12</sub> and the "kitten"|title=Computational group theory (Durham, 1982)|publisher=Academic Press|place=London|year=1984|isbn=978-0-12-066270-8|mr=0760669|editor-first=Michael D.|editor-last=Atkinson|pages=353–358}} * {{citation|first1=D. R.|last1=Hughes|first2=F. C.|last2=Piper|title=Design Theory|publisher=Cambridge University Press|isbn=978-0-521-35872-9|pages=173–176|year=1985}}. * {{Citation |last= Kirkman |first=Thomas P. |author-link= Thomas Kirkman |title= On a Problem in Combinations |journal= The Cambridge and Dublin Mathematical Journal |volume= II |pages= 191–204 |year= 1847 |postscript= .}} * {{citation|last1=Lindner|first1=C.C.|last2=Rodger|first2=C.A.|title=Design Theory|year=1997|publisher=CRC Press|location=Boca Raton|isbn=978-0-8493-3986-8}} * {{citation|last1=Östergard|first1=Patric R.J.|last2=Pottonen |first2=Olli|title=There exists no Steiner system S(4,5,17)|journal=[[Journal of Combinatorial Theory]]|series=Series A|year=2008|volume=115|issue=8|pages=1570–1573|doi=10.1016/j.jcta.2008.04.005|doi-access=free}} * {{citation|first=J.|last=Steiner|author-link=Jakob Steiner|title=Combinatorische Aufgabe|journal=[[Crelle's Journal|Journal für die reine und angewandte Mathematik]]|volume=1853|issue=45|year=1853|pages=181–182|doi=10.1515/crll.1853.45.181|s2cid=199547187 |url=https://zenodo.org/record/1448866}}. * {{citation|doi=10.1007/BF02948947|last=Witt|first=Ernst|author-link=Ernst Witt|title=Die 5-Fach transitiven Gruppen von Mathieu|journal=Abh. Math. Sem. Univ. Hamburg|volume=12|pages=256–264|year=1938|s2cid=123658601 }} == External links == {{Commons category|Steiner systems}} *{{MathWorld|title=Steiner System|urlname=SteinerSystem|author=Rowland, Todd|author2=Weisstein, Eric W.|name-list-style=amp}} *{{springer|title=Steiner system|id=Steiner_system|last=Rumov|first=B.T.}} * [http://www.win.tue.nl/~aeb/graphs/S.html Steiner systems] by Andries E. Brouwer * [http://hilltop.bradley.edu/~delgado/gandg/SteinerApplet.html Implementation of S(5,8,24)] by Dr. Alberto Delgado, Gabe Hart, and Michael Kolkebeck * [https://archive.today/20121220072522/http://www.xs4all.nl/~jemebius/Steiner5824.htm S(5, 8, 24) Software and Listing] by Johan E. Mebius {{Incidence structures}} [[Category:Combinatorial design]] [[Category:Design of experiments]] [[Category:Families of sets]] [[de:Steiner-Tripel-System]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Citation
(
edit
)
Template:Cite arXiv
(
edit
)
Template:Cite journal
(
edit
)
Template:Cite web
(
edit
)
Template:Commons category
(
edit
)
Template:Harvnb
(
edit
)
Template:Harvs
(
edit
)
Template:Incidence structures
(
edit
)
Template:Isbn
(
edit
)
Template:Math
(
edit
)
Template:MathWorld
(
edit
)
Template:Mvar
(
edit
)
Template:NoteFoot
(
edit
)
Template:NoteTag
(
edit
)
Template:Nowrap
(
edit
)
Template:Reflist
(
edit
)
Template:Sfn
(
edit
)
Template:SfnRef
(
edit
)
Template:Short description
(
edit
)
Template:Sister project
(
edit
)
Template:Springer
(
edit
)