Steiner rendszer

A Steiner-rendszer ( Jacob Steinerről kapta a nevét ) a blokkdiagramok egy változata , pontosabban egy t-séma , ahol λ = 1 és t ≥ 2.

Egy Steiner-rendszer t , k , n paraméterekkel (írva S( t , k , n )) egy n elemű S halmaz S egy k elemű részhalmazaival együtt ( blokkoknak nevezett ) azzal a tulajdonsággal, hogy minden t - pontosan egy blokkban található S elem részhalmaza . Az alternatív blokkdiagram jelölésben az S( t , k , n )-t t- ( n , k )-ként jelöljük,1) séma.

Ez a definíció viszonylag új, és általánosítja a Steiner-rendszer klasszikus definícióját, amely emellett megköveteli, hogy k = t + 1. Az S(2,3, n ) áramkör Steiner-hármas rendszer volt (és hívják ma is) , S(3 ) ,4, n ) Steiner-négyes rendszernek nevezték , és így tovább. A definíció általánosítása után az elnevezési rendszer nem érvényesül olyan szigorúan.

Az áramkörelméletben sokáig ismeretlen volt, hogy létezik-e nem triviális ( t < k < n ) Steiner-rendszer, amelynek t ≥ 6, és azt sem, hogy végtelen sok olyan áramkör van-e, amelynek t = 4 vagy 5 [1] . Igenlő választ adott Peter Kivash 2014-ben [2] [3] [4] .

Példák

Véges projektív síkok

Egy q rendű véges projektív sík , amelyben az egyenesek blokkok, S(2, q + 1, q 2 + q + 1) , mert q 2 + q + 1 pontja van, minden egyenes q + 1 ponton megy át, és mindegyik a pár különálló pont pontosan ugyanazon az egyenesen helyezkedik el.

Véges affin síkok

Egy q rendű véges affin sík , amelyben a vonalak blokkként szerepelnek, az S(2,  q ,  q 2 ) séma . Egy q rendű affin síkot kaphatunk egy azonos rendű projektív síkból, ha egy blokkot és annak minden pontját eltávolítjuk a projektív síkból. Ha más blokkokat választ az eltávolításra, nem izomorf affin síkokat kaphat.

Klasszikus Steiner rendszerek

Steiner hármas rendszerek

Az S(2,3, n ) áramkört Steiner-hármas rendszernek , a blokkjait pedig tripláknak nevezzük . Az STS( n ) jelölést gyakran használják a Steiner-hármas rendszerekre . A ponton áthaladó hármasok száma (n-1)/2 , így a hármasok teljes száma n ( n −1)/6. Ez azt mutatja, hogy n - nek 6k+1 -nek vagy 6k+3 -nak kell lennie valamilyen k esetén . Azt a tényt, hogy ez a feltétel n -re elegendő az S(2,3, n ) létezéséhez, Ray Chandra Bose [5] és T. Skolem [6] bizonyította . A 2. rendű projektív sík ( Fano sík ) az STS(7), a 3. rendű affin sík pedig az STS(9).

Az izomorfizmusig az STS(7) és az STS(9) egyediek. Két STS(13) séma létezik, 80 STS(15) séma és 11 084 874 829 STS(19) séma [7] .

Megadhatjuk a szorzást egy S halmazon a Steiner-hármas rendszer segítségével, ha aa = a -t állítunk be S - ből minden a -ra, és ab = c -t, ha { a , b , c } egy Steiner-hármas. Ez S -t idempotens kommutatív kvázicsoporttá teszi . Egy kvázicsoportnak van egy további tulajdonsága, hogy az ab = c azt jelenti , hogy bc = a és ca = b [comm. 1] . Ezzel szemben bármely (véges) kvázicsoport ilyen tulajdonságokkal a Steiner-hármasok rendszeréből adódik. Azokat a kommutatív idempotens kvázicsoportokat, amelyek kielégítik ezt a további tulajdonságot, Steiner-kvázicsoportoknak nevezzük [8] .

Steiner négyes rendszere

Az S(3,4, n ) sémát Steiner-négyes rendszernek nevezzük . S(3,4, n ) létezésének szükséges és elégséges feltétele n 2 vagy 4 (mod 6). Az SQS( n ) jelölést gyakran használják ezekre a rendszerekre .

Az izomorfizmusig az SQS(8) és az SQS(10) egyediek, 4 SQS(14) és 1.054.163 SQS(16) séma létezik [9] .

Steiner ötös rendszerek

Az S(4,5, n ) sémát Steiner ötszögrendszerének nevezzük . Egy ilyen rendszer létezésének szükséges feltétele az n 3 vagy 5 (mod 6), ami az összes klasszikus Steiner-rendszerre érvényes konvenciókból következik. Az általános rendszerek további feltétele, hogy n 4 (mod 5), abból adódik, hogy a blokkok számának egész számnak kell lennie. A megfelelő feltételek nem ismertek.

Egyetlen 11. rendű Steiner-pentad rendszer létezik, de 15. vagy 17. rendű rendszer nincs [10] . Ismeretesek a 23., 35., 47., 71., 83., 107., 131., 167. és 243. rendű rendszerek. A legkisebb rendelés, amelynek létezése ismeretlen (2011-ben), a 21.

Tulajdonságok

S( t , k , n ) definíciójából egyértelmű, hogy . (Az egyenlőségek, bár technikailag lehetségesek, triviális rendszerekhez vezetnek.)

Ha létezik S( t , k , n ) rendszer , akkor egy bizonyos elemet tartalmazó blokkok kiválasztása és az elem törlése egy S( t −1, k −1, n −1) származtatott rendszert eredményez . Így az S( t −1, k −1, n − 1) létezése szükséges feltétele az S( t , k , n ) séma létezésének .

A t elemű részhalmazok száma S - ben, míg a t -elemű részhalmazok száma az egyes blokkban . Mivel bármely t elemű részhalmaz pontosan egy blokkban található, így kapjuk a , or -t

ahol b  a blokkok száma. Hasonló érvelés egy adott elemet tartalmazó t elemű részhalmazokról ad nekünk , vagy

=

ahol r  a kiválasztott elemet tartalmazó blokkok száma. Az egyenlőség ezekből a meghatározásokból következik . Az S( t , k , n ) áramkör létezésének szükséges feltétele, hogy b és r integrálok legyenek . Mint minden blokkdiagram esetében, a Fisher-egyenlőtlenség igaz a Steiner rendszerekre.

Adott az S( t,k,n ) Steiner-rendszerparaméterek és egy méret részhalmaz , amely legalább egy blokkban található, Pascal-háromszög [11] megszerkesztésével megszámolhatjuk, hogy hány blokk metszi ezt a részhalmazt meghatározott számú elemmel . Különösen az, hogy egy tetszőleges számú elemet tartalmazó rögzített blokkon keresztező blokkok száma nem függ a blokk kiválasztásától.

Az i elemű pontkészletet tartalmazó blokkok száma :

számára

Megmutatható, hogy ha létezik S(2, k , n ) Steiner rendszer , ahol k egy 1-nél nagyobb prímhatvány, akkor n 1 vagy k (mod k ( k −1)) . Különösen az S(2, 3, n ) Steiner hármas rendszernek n = 6 m + 1 vagy 6 m + 3 kell legyen . Mint már említettük, ez az egyetlen megszorítása a Steiner-hármas rendszereknek, vagyis minden m természetes számra létezik S(2, 3, 6 m + 1) és S(2, 3, 6 m + 3) rendszerek . .

Történelem

A Steiner hármas rendszerek voltak az elsők, amelyek meghatározták a V.S.B. Woolhouse 1844-ben a Lady's and Gentlemen's Diary 1733-as prémium számában [12] . A problémát Thomas Kirkman [13] oldotta meg . 1850-ben Kirkman felvetette a probléma egy változatát „ Kirkman iskoláslány-problémája ” néven, amely hármasok rendszerét kéri további tulajdonsággal (megoldhatóság). Kirkman munkásságának ismerete nélkül Jacob Steiner [14] meghatározta a hármasok rendszerét, és munkája híresebb lett, így a rendszert róla nevezték el.

Mathieu csoportok

A Steiner rendszerek néhány példája szorosan kapcsolódik a csoportelmélethez . Konkrétan véges egyszerű csoportok , amelyeket Mathieu-csoportoknak neveznek , Steiner-rendszerek automorfizmuscsoportjaiként keletkeznek :

A Steiner rendszer S(5, 6, 12)

Egyedülálló Steiner rendszer S(5,6,12). Automorfizmuscsoportja az M 12 Mathieu-csoport , és ebben az összefüggésben a csoportot W 12 -vel jelöljük .

Épületek

Az S(5,6,12) rendszer felépítésének többféle módja van.

Projektív vonalmetódus

Ez a konstrukció Carmichaelnek (1937) [15] köszönhető .

Az F 11 véges mező 11 eleméhez (azaz modulo 11 maradékokhoz) adunk egy új elemet, amelyet ∞ -vel jelölünk . Ez a 12 elemből álló S halmaz formálisan azonosítható az F 11 feletti projektív egyenes pontjaival . Nevezzük a következő 6-os méretű részhalmazt,

"Blokk". Ennek a blokknak a segítségével megkapjuk az S (5,6,12) áramkör többi blokkját a lineáris-tört transzformáció ismételt alkalmazásával :

ahol a,b,c,d az F 11 -ben, az ad - bc pedig egy nullától eltérő négyzet az F 11 -ben . Ha definiáljuk f (− d / c ) = ∞ és f (∞) = a / c , akkor ez a függvény leképezi önmagára az S halmazt. Geometriai nyelven ezek a projektív egyenes vetületei. Szuperpozícióval alkotnak egy csoportot , és ez a csoport a 660-as rendű PSL (2,11) projektív speciális lineáris csoport . Ebben a csoportban pontosan öt olyan elem található, amelyek a kezdeti blokkot változatlanul hagyják [16] , így 132 képünk van a háztömb. Az ezen a halmazon ható csoport multiplikatív tranzitivitása következtében az S halmaz öt elemének bármely részhalmaza pontosan ezen a 132 hatos méretű képen fog megjelenni.

Curtis módszer

A W 12 áramkör alternatív felépítését R. T. Curtis [17] módszerének alkalmazásával kapjuk meg , amely a blokkok egyenkénti "kézi kiszámítására" szolgál. A Curtis-módszer 3x3-as számtáblázatok kitöltésén alapul, amelyek egy affin geometriát reprezentálnak egy F 3 xF 3 vektortéren , az S(2,3,9) rendszeren.

Konstrukció a gráf felosztásával K 6

A K 6 teljes gráf tényezői közötti kapcsolat az S(5,6,12) [18] sémát generálja . A K 6 grafikonnak 6 különböző 1-tényezője van (az élek tökéletes illeszkedésre való felosztásának útja ), valamint 6 csúcsa. A csúcsok halmaza és a faktorizációk halmaza blokkot ad. Minden faktorizációs párhoz pontosan egy közös tökéletes egyezés létezik. Vegyünk egy csúcskészletet, és cseréljük le az általános tökéletes illeszkedés élének megfelelő két csúcsot a faktorizációknak megfelelő címkére. Adjuk hozzá az eredményt egy blokkkészlethez. Ismételjük meg a folyamatot a teljes tökéletes illeszkedés fennmaradó két élére. Egyszerűen veszünk egy sor faktorizációt, és lecseréljük a két faktorizációnak megfelelő címkéket egy él végpontjaira általános tökéletes illeszkedésben. Ezt megismételjük a másik két illeszkedő élnél. Minden faktorizációs párhoz 3+3 = 6 blokk tartozik, a 6 faktorizáció között pedig 6C2 = 15 pár van, ami 90 új blokkot ad. Végül 12-ből 6 objektumból összesen 12C6 = 924 kombinációt veszünk, és elvetünk minden olyan kombinációt, amely 5 vagy több közös objektummal rendelkezik a 92 blokk bármelyikével. Pontosan 40 blokk marad, ami 2+90+40 = 132 S(5,6,12) blokkot ad.

A Steiner rendszer S(5, 8, 24)

Az S(5, 8, 24) Steiner-rendszert, más néven Witt- sémát vagy Witt-geometriát , Robert Carmichael [19] írta le, és Witt [20] fedezte fel újra . Ez a rendszer számos szórványos csoporttal és egy kivételes 24 dimenziós ráccsal , a Leach grid néven ismert .

Az S(5, 8, 24) séma automorfizmuscsoportja az M 24 Mathieu-csoport , és a sémák kontextusában W 24 ("W" a "Witt"-ből)

Épületek

Az S(5,8,24) megalkotásának számos módja van. Itt két módszert ismertetünk:

24 elem 8-as csoportokban való kombinálásán alapuló módszer

A 24 elemből álló halmaz összes 8 elemű részhalmaza lexikográfiai sorrendben jön létre, és minden olyan részhalmaz, amely háromnál kevesebb helyen különbözik valamelyik részhalmaztól, el lesz vetve.

Nyolcas lista a 01, 02, 03, ..., 22, 23, 24 elemekhez:

01 02 03 04 05 06 07 08 01 02 03 04 09 10 11 12 01 02 03 04 13 14 15 16 . . (a következő 753 nyolcas kimaradt) . 13 14 15 16 17 18 19 20 13 14 15 16 21 22 23 24 17 18 19 20 21 22 23 24

Minden egyes elem 253-szor fordul elő bármely nyolcasban. Minden pár 77 alkalommal találkozik. Minden hármas 21-szer fordul elő. Minden négyes 5 alkalommal fordul elő. Minden ötös egyszer találkozik. Nem minden hat, hét vagy nyolc található.

24 bites bináris karakterláncokon alapuló módszer

Minden 24 bites bináris karakterlánc lexikográfiai sorrendben jön létre, és minden olyan karakterlánc, amely kevesebb, mint 8 pozícióval különbözik a korábban talált karakterlánctól, eldobásra kerül. Ennek eredményeként a következőket kapjuk:

00000000000000000000000 000000000000000011111111 000000000000111100001111 000000000000111111110000 000000000011001100110011 000000000011001111001100 000000000011110000111100 000000000011110011000011 000000000101010101010101 000000000101010110101010 . . (a következő 4083 24 bites sor kimaradva) . 111111111111000011110000 111111111111111100000000 111111111111111111111111

A lista 4096 elemet tartalmaz, amelyek a kiterjesztett bináris Golay-kód kódszavai . Az XOR művelettel csoportot alkotnak . Az egyik szó 0 bites, 759 szó nyolc 1 bites, 2576 szó 12 1 bites, 759 szó 16 1 bites, és egy szó mind 1 bites. Az S(5,8,24) minta 759 8 elemű blokkját 1 bites szavak határozzák meg nyolc 1-essel.

Lásd még

Megjegyzések

  1. ↑ Ez a tulajdonság ekvivalens (xy)y = x minden x és y esetén egy idempotens kommutatív kvázicsoportban.

Jegyzetek

  1. ↑ Enciklopédia .
  2. ↑ Keevash, 2014 .
  3. ↑ Quanta Magazin .
  4. ↑ Kalai .
  5. ↑ Bose, 1939 , p. 353–399.
  6. ↑ Skolem, 1958 , p. 273–280.
  7. ↑ Colbourn, Dinitz, 2007 , p. 60.
  8. ↑ Colbourn, Dinitz, 2007 , p. 497, definíció 28.12.
  9. ↑ Colbourn, Dinitz, 2007 , p. 106.
  10. ↑ Östergard, Pottonen, 2008 .
  11. ↑ Assmus, Key, 1992 , p. nyolc.
  12. ↑ Lindner és Rodger 1997 , p. 3.
  13. ↑ Kirkman, 1847 .
  14. ↑ Steiner, 1853 .
  15. ↑ Carmichael, 1956 , p. 431.
  16. ↑ Beth, Jungnickel, Lenz, 1986 , p. 196.
  17. ↑ Curtis, 1984 .
  18. ↑ EAGTS tankönyv . Letöltve: 2017. július 5. Az eredetiből archiválva : 2017. december 10.
  19. ↑ Carmichael, 1931 .
  20. ↑ Witt, 1938 .

Irodalom

  • Encyclopaedia of Design Theory: t-Designs . Designtheory.org (2004. október 4.). Letöltve: 2012. augusztus 17.
  • RC Bose. A kiegyensúlyozott hiányos blokktervek felépítéséről  // Ann. Eugenika 9. - 1939. - S. 353-399 .  (nem elérhető link)
  • Peter Keevash. A tervek létezése . — 2014.
  • T. Skolem. Néhány megjegyzés Steiner hármas rendszereiről  // Math. Scand. 6. - 1958. - S. 273-280 .
  • Egy tervezési dilemma megoldva, mínusz Designs . Quanta Magazin (2015. június 9.). Letöltve: 2015. június 27.
  • Gil Kalai. Tervek léteznek! . http://www.bourbaki.ens.fr . S'eminaire BOURBAKI.
  • E. F. Assmus, J. D. Key. Tervek és kódjaik. - Cambridge: Cambridge University Press, 1992. - ISBN 0-521-41361-3 .
  • Thomas Beth, Dieter Jungnickel, Hanfried Lenz. tervezési elmélet. - Cambridge: Cambridge University Press , 1986. - ISBN 978-0-521-44432-3 .
  • Robert Carmichael. Tactical Configurations of Rank Two  // American Journal of Mathematics. - 1931. - T. 53 . – S. 217–240 . - doi : 10.2307/2370885 . — .
  • Robert Carmichael. Bevezetés a véges rendű csoportok elméletébe. - Dover, 1956. - ISBN 0-486-60300-8 .
  • Charles J. Colbourn, Jeffrey H. Dinitz. A kombinatorikus tervezés kézikönyve. — 2. — Boca Raton: Chapman & Hall/CRC, 2007. — ISBN 1-58488-506-8 .
  • RT Curtis. A Steiner-rendszer S(5,6,12), a Mathieu-csoport M 12 és a "cica" // Számítógépes csoportelmélet (Durham, 1982). - London: Academic Press, 1984. - S. 353-358. — ISBN 0-12-066270-1 .
  • D. R. Hughes, E. C. Piper. tervezési elmélet . - Cambridge: Cambridge University Press, 1985. -  173-176 . - ISBN 0-521-25754-9 .
  • Thomas P. Kirkman. A kombinációk problémájáról // The Cambridge and Dublin Mathematical Journal. - Macmillan, Barclay és Macmillan, 1847. - II . köt. – S. 191–204 .
  • CC Lindner, CA Rodger. Tervezéselmélet . - Boca Raton: CRC Press, 1997. - ISBN 0-8493-3986-3 .
  • Patric RJ Östergard, Olli Pottonen. Nem létezik Steiner-rendszer S(4,5,17) // Journal of Combinatorial Theory Series A. - 2008. - Vol. 115 , no. 8 . - S. 1570-1573 . - doi : 10.1016/j.jcta.2008.04.005 .
  • J. Steiner. Combinatorische Aufgabe // Journal für die Reine und Angewandte Mathematik . - 1853. - T. 45 . – S. 181–182 .
  • Ernst Witt. Die 5-Fach transitiven Gruppen von Mathieu // Abh. Math. Sem. Univ. Hamburg. - 1938. - T. 12 . – S. 256–264 . - doi : 10.1007/BF02948947 .

Linkek