Steinerův systém: Porovnání verzí

← Přejít na předchozí porovnání Přejít na další porovnání →

Smazaný obsah Přidaný obsah

V textu

Verze z 22. 4. 2021, 10:33

Steinerův systém $S(t,k,v)$ , $2\leq t<k<v$ , podle matematika Jakoba Steinera, je konečná kombinatorická struktura - systém $k-$ prvkových podmnožin základní $v-$ prvkové množiny (tzv. bloků) s vlastností, že každých $t$ bodů leží společně v právě jednom bloku. Steinerovy systémy zobecňují konečné geometrie, které odpovídají $S(2,k,v)$ : v geometrii každé dva body určují právě jednu přímku.

Existence Steinerových systémů

Základním matematickým problémem Steinerových systémů je, zda pro daná $t,k,v$ vůbec $S(t,k,v)$ existuje. Tento problém je až na výjimky otevřený; výjimky určuje několik známých konstrukcí $S(t,k,v)$ a naopak několik podmínek, které pro jiná $t,k,v$ existenci vylučují.

Utržením jednoho bodu ze Steinerova systému $S(t,k,v)$ získáme po odstranění bloků, v nichž tento bod neležel, tzv. derivovaný systém $S(t,k,v)$ Derivovaný systém také musí splňovat axiomy Steinerova systému, jeho derivovaný systém také atd. Z toho plyne soustava nutných podmínek pro existenci $S(t,k,v)$ :

{\frac {\left({\begin{array}{c}v-i\\t-i\\\end{array}}\right)}{\left({\begin{array}{c}k-i\\t-i\\\end{array}}\right)}}

musí být celočíselné pro každé

0<i<t

^[1]

Zlomek vyjadřuje počet bloků, v nichž leží každá $i-$ tice bodů.

Splnění této sady podmínek však stále není postačující pro existenci $S(t,k,v)$ ; již vyvráceny byly například existence $S(4,5,15)$ , $S(4,10,66)$ či $S(3,13,145)$

Pro $t>3$ známe (nebo dovedeme prokázat existenci) jen konečně mnoho Steinerových systémů; pro $6\leq t$ žádný.

Dosud známé nekonečné třídy Steinerových systémů^[2]

$S(2,q,q^{n})$ pro $q=$ mocnina prvočísla a $n>1$ (afinní geometrie)
$S(3,q+1,q^{n}+1)$ pro $q=$ mocnina prvočísla a $n>1$ (sférické geometrie)
$S(2,q+1,(q^{n+1}-1)/(q-1))$ pro $q=$ mocnina prvočísla a $n>1$ (projektivní geometrie)
$S(2,q+1,q^{3}+1)$ pro $q=$ mocnina prvočísla
$S(2,2^{r},2^{r+s}+2^{r}-2^{s})$ pro $1<r<s$ (Dennistonův design)

Steinerovy systémy v teorii grup

Speciální Steinerovy systémy jsou jednou z ekvivalentních možností jak definovat vysoce tranzitivní Mathieu grupy:

$5-$ transitivní Mathieu grupa $M_{24}$ je grupou automorfismů Steinerova systému $S(5,8,24)$
$5-$ transitivní Mathieu grupa $M_{12}$ je grupou automorfismů Steinerova systému $S(5,6,12)$
$4-$ transitivní Mathieu grupa $M_{23}$ je grupou automorfismů Steinerova systému $S(4,7,23)$
$4-$ transitivní Mathieu grupa $M_{11}$ je grupou automorfismů Steinerova systému $S(4,5,11)$
$3-$ transitivní Mathieu grupa $M_{22}$ je grupou automorfismů Steinerova systému $S(3,6,22)$

↑ BIGGS, Norman L.; WHITE, Arthur T. Permutation groups and combinatorial structures. [s.l.]: Cambridge University Press, 1979. 140 s. ISBN 978-0521222877.
↑ COLBOURN, Charles J.; DINITZ, Jeffrey H. Handbook of combinatorial designs. II.. vyd. [s.l.]: CRC Press, 2006. 1016 s. ISBN 9780429138485. S. 102-110.

[1] BIGGS, Norman L.; WHITE, Arthur T. Permutation groups and combinatorial structures. [s.l.]: Cambridge University Press, 1979. 140 s. ISBN 978-0521222877.

[2] COLBOURN, Charles J.; DINITZ, Jeffrey H. Handbook of combinatorial designs. II.. vyd. [s.l.]: CRC Press, 2006. 1016 s. ISBN 9780429138485. S. 102-110.

[1]

[2]

@@ Řádek 16: / Řádek 16: @@
  t-i \\
 \end{array}
-\right)} </math> musí být celočíselné pro každé <math> 0<i<t </math>
+\right)} </math> musí být celočíselné pro každé <math> 0<i<t </math><ref>{{Citace monografie
+| příjmení = Biggs
+| jméno = Norman L.
+| příjmení2 = White
+| jméno2 = Arthur T
+| titul = Permutation groups and combinatorial structures
+| vydavatel = Cambridge University Press
+| rok vydání = 1979
+| počet stran = 140
+| isbn = 978-0521222877
+}}</ref>
 Zlomek vyjadřuje počet bloků, v nichž leží každá <math>i-</math>tice bodů.

Verze z 22. 4. 2021, 10:33

Existence Steinerových systémů

Dosud známé nekonečné třídy Steinerových systémů[2]

Steinerovy systémy v teorii grup

Dosud známé nekonečné třídy Steinerových systémů^[2]