Blokový design - Block design
v kombinační matematika, a blokový design je struktura výskytu sestávající ze sady společně s a rodina podmnožin známý jako bloky, vybráno tak, aby frekvence prvků splňovala určité podmínky, díky nimž se kolekce bloků projevuje symetrie (Zůstatek). Mají aplikace v mnoha oblastech, včetně experimentální design, konečná geometrie, fyzikální chemie, testování softwaru, kryptografie, a algebraická geometrie.
Termín bez dalších specifikací blokový design obvykle se odkazuje na a vyvážený neúplný design bloku (BIBD), konkrétně (a také synonymně) a 2-design, který byl historicky nejintenzivněji studovaným typem díky jeho aplikaci v návrh experimentů.[1][2] Jeho zobecnění je známé jako t-design.
Přehled
Design se říká, že je vyrovnaný (až do t) padám t-subsety původní sady se vyskytují ve stejném množství (tj. λ) bloky. Když t je nespecifikováno, lze jej obvykle považovat za 2, což znamená, že každý pár prvků se nachází ve stejném počtu bloků a design je párově vyvážené. Pro t= 1, každý prvek se vyskytuje ve stejném počtu bloků ( reprodukční číslo, označeno r) a design se říká pravidelný. Jakýkoli design vyvážený až t je také vyvážený ve všech nižších hodnotách t (i když s různými λ-values), takže například párově vyvážený (t= 2) design je také pravidelný (t= 1). Když požadavek na vyvážení selže, návrh může být stále částečně vyvážený pokud t-podskupiny lze rozdělit na n třídy, každá s vlastní (jinou) λ-hodnota. Pro t= 2 tyto jsou známé jako PBIBD (n) designy, jejíž třídy tvoří asociační schéma.
O designech se obvykle říká (nebo se předpokládá), že jsou neúplný, což znamená, že žádný blok neobsahuje všechny prvky množiny, což vylučuje triviální design.
Návrh bloku, ve kterém mají všechny bloky stejnou velikost (obvykle označeny k) je nazýván jednotný nebo správně. Designy diskutované v tomto článku jsou jednotné. Rovněž byly studovány blokové vzory, které nemusí být nutně jednotné; pro t= 2 jsou v literatuře známy pod obecným názvem párově vyvážené vzory (PBD).
Blokové vzory mohou nebo nemusí mít opakované bloky. Volají se designy bez opakovaných bloků jednoduchý,[3] v takovém případě je „skupina“ bloků a soubor spíše než a multiset.
v statistika lze koncept blokového designu rozšířit na nebinární blokové vzory, ve kterých bloky mohou obsahovat více kopií prvku (viz blokování (statistika) ). Tam se volá design, ve kterém se každý prvek vyskytuje stejný celkový počet opakování rovnocenné, což znamená a pravidelný design, pouze pokud je design také binární. Matice dopadů nebinárního designu uvádí, kolikrát se každý prvek opakuje v každém bloku.
Pravidelné jednotné vzory (konfigurace)
Nejjednodušší typ „vyváženého“ designu (t= 1) je znám jako a taktická konfigurace nebo 1-design. Korespondence struktura výskytu v geometrie je známá jednoduše jako konfiguraceviz Konfigurace (geometrie). Takový design je jednotný a pravidelný: každý blok obsahuje k prvky a každý prvek je obsažen v r bloky. Počet nastavených prvků proti a počet bloků b jsou ve vztahu , což je celkový počet výskytů prvků.
Každý binární matice s konstantními součty řádků a sloupců je matice výskytu pravidelného jednotného blokového designu. Každá konfigurace má také odpovídající biregular bipartitní graf známý jako jeho výskyt nebo Leviho graf.
Párově vyvážené jednotné vzory (2-vzory nebo BIBD)
Vzhledem k konečné sadě X (prvků zvaných bodů) a celá čísla k, r, λ ≥ 1, definujeme a 2-design (nebo BIBD, stojící pro vyvážený neúplný design bloku) B být rodinou k-prvkové podmnožiny X, volala bloky, takový, že jakýkoli X v X je obsažen v r bloky a jakýkoli pár odlišných bodů X a y v X je obsažen v λ bloky.
Tady proti (počet prvků X, nazývané body), b (počet bloků), k, r, a λ jsou parametry designu. (Aby se zabránilo zvrhlým příkladům, předpokládá se také, že proti > k, takže žádný blok neobsahuje všechny prvky sady. To je význam názvu „neúplné“ v názvu těchto návrhů.) V tabulce:
proti body, počet prvků X b počet bloků r počet bloků obsahujících daný bod k počet bodů v bloku λ počet bloků obsahujících libovolné 2 (nebo obecněji) t) odlišné body
Design se nazývá (proti, k, λ) design nebo (proti, b, r, k, λ)-design. Parametry nejsou všechny nezávislé; proti, k, a λ určit b a r, a ne všechny kombinace proti, k, a λ jsou možné. Dvě základní rovnice spojující tyto parametry jsou
získá se spočítáním počtu párů (B, p) kde B je blok a p je bod v tomto bloku a
získané z počtu trojnásobků (p, q, B) kde p a q jsou odlišné body a B je blok, který je obsahuje oba, a vydělením tohoto počtu proti.
Tyto podmínky nejsou dostatečné, protože například návrh (43,7,1) neexistuje.[4]
The objednat 2-designu je definován jako n = r − λ. The doplněk 2-designu se získá nahrazením každého bloku jeho doplňkem v množině bodů X. Je to také 2-design a má parametry proti′ = proti, b′ = b, r′ = b − r, k′ = proti − k, λ′ = λ + b − 2r. 2-design a jeho doplněk mají stejné pořadí.
Základní věta, Fisherova nerovnost, pojmenovaný po statistikovi Ronald Fisher, je to b ≥ proti v jakémkoli 2-provedení.
Příklady
Unikátní (6,3,2) design (proti = 6, k = 3, λ = 2) má 10 bloků (b = 10) a každý prvek se opakuje 5krát (r = 5).[5] Pomocí symbolů 0-5 jsou bloky následující trojice:
- 012 013 024 035 045 125 134 145 234 235.
a odpovídající matice výskytu (A proti×b binární matice s konstantním součtem řádků r a konstantní součet sloupců k) je:
Jeden ze čtyř neizomorfních (8,4,3) návrhů má 14 bloků, přičemž každý prvek se opakuje 7krát. Pomocí symbolů 0-7 jsou bloky následující 4-n-tice:[5]
- 0123 0124 0156 0257 0345 0367 0467 1267 1346 1357 1457 2347 2356 2456.
Jedinečný design (7,3,1) je symetrický a má 7 bloků, přičemž každý prvek se opakuje třikrát. Pomocí symbolů 0-6 jsou bloky následující trojice:[5]
- 013 026 045 124 156 235 346.
Tento design je spojen s Fano letadlo, s prvky a bloky návrhu odpovídající k bodům a liniím roviny. Odpovídající matice dopadů může být také symetrická, pokud jsou štítky nebo bloky tříděny správným způsobem:
Symetrické 2 vzory (SBIBD)
Případ rovnosti v Fisherově nerovnosti, tj. 2-design se stejným počtem bodů a bloků, se nazývá a symetrický design.[6] Symetrické vzory mají nejmenší počet bloků ze všech 2 vzorů se stejným počtem bodů.
V symetrickém designu r = k drží stejně jako b = proti, a i když to obecně není pravda v libovolných 2-designech, v symetrickém designu se setkávají každé dva odlišné bloky λ bodů.[7] Věta o Ryser poskytuje konverzaci. Li X je proti- sada prvků a B je proti-prvková sada k-prvkové podmnožiny ("bloky"), takže jakékoli dva odlišné bloky mají společné přesně λ body, poté (X, B) je symetrický blokový design.[8]
Parametry symetrického designu splňují
To ukládá přísná omezení proti, takže počet bodů zdaleka není libovolný. The Věta Bruck – Ryser – Chowla dává nezbytné, ale ne dostatečné podmínky pro existenci symetrického designu z hlediska těchto parametrů.
Níže jsou uvedeny důležité příklady symetrických 2 návrhů:
Projektivní roviny
Konečné projektivní roviny jsou symetrické 2-vzory s λ = 1 a objednat n > 1. U těchto návrhů se symetrická rovnice návrhu stane:
Od té doby k = r můžeme napsat řád projektivní roviny tak jako n = k - 1 a ze zobrazené rovnice výše získáme proti = (n + 1)n + 1 = n2 + n + 1 body v projektivní rovině řádu n.
Protože projektivní rovina je symetrický design, máme b = proti, znamenající, že b = n2 + n + 1 také. Číslo b je počet řádky projektivní roviny. Vzhledem k tomu, že λ = 1 nelze opakovat žádné řádky, takže projektivní rovina je jednoduchý 2-design, ve kterém jsou počet řádků a počet bodů vždy stejný. Pro projektivní rovinu k je počet bodů na každém řádku a je roven n + 1. Podobně, r = n +1 je počet řádků, se kterými je daný bod v incidentu.
Pro n = 2 dostaneme projektivní rovinu řádu 2, nazývanou také Fano letadlo, s proti = 4 + 2 + 1 = 7 bodů a 7 řádků. V rovině Fano má každá čára n + 1 = 3 body a každý bod patří n + 1 = 3 řádky.
Je známo, že projektivní roviny existují pro všechny řády, které jsou prvočísly nebo mocninami prvočísel. Tvoří jedinou známou nekonečnou rodinu (s ohledem na konstantní hodnotu λ) symetrických blokových vzorů.[9]
Dvojplošníky
A dvojplošník nebo geometrie dvojplošníku je symetrický 2-design s λ = 2; to znamená, že každá sada dvou bodů je obsažena ve dvou blocích („řádcích“), zatímco jakékoli dvě linie se protínají ve dvou bodech.[9] Jsou podobné konečným projektivním rovinám, až na to, že místo dvou bodů určujících jednu čáru (a dvou čar určujících jeden bod) určují dva body dvě čáry (respektive body). Dvojplošník řádu n je ten, jehož bloky mají k = n + 2 body; má to proti = 1 + (n + 2)(n + 1) / 2 body (od r = k).
18 známých příkladů[10] jsou uvedeny níže.
- (Triviální) Dvojplošník řádu 0 má 2 body (a řádky velikosti 2; provedení 2- (2,2,2)); jsou to dva body se dvěma bloky, z nichž každý se skládá z obou bodů. Geometricky je to digon.
- Dvojplošník řádu 1 má 4 body (a čáry velikosti 3; provedení 2- (4,3,2)); je to kompletní design s proti = 4 a k = 3. Geometricky jsou body vrcholy a bloky plochami čtyřstěnu.
- Dvojplošník řádu 2 je doplňkem Fano letadlo: má 7 bodů (a řádky velikosti 4; a 2- (7,4,2)), kde jsou řádky uvedeny jako doplňuje (3bodových) čar v rovině Fano.[11]
- Dvojplošník řádu 3 má 11 bodů (a čáry velikosti 5; a 2- (11,5,2)) a je také známý jako Paley dvojplošník po Raymond Paley; je spojen s Paley digraph řádu 11, který je sestaven pomocí pole s 11 prvky, a je Hadamard 2-design spojené s Hadamardovou maticí velikosti 12; vidět Paley stavba I.
- Algebraicky to odpovídá výjimečnému vložení projektivní speciální lineární skupina PSL(2,5) palce PSL(2,11) - viz projektivní lineární skupina: akce na p bodů pro detaily.[12]
- Existují tři dvojplošníky řádu 4 (a 16 bodů, řádky velikosti 6; a 2- (16,6,2)). Jedním z nich je Konfigurace Kummer. Tyto tři vzory jsou také Menon designy.
- Existují čtyři dvojplošníky řádu 7 (a 37 bodů, řádky velikosti 9; a 2- (37,9,2)).[13]
- Existuje pět dvojplošníků řádu 9 (a 56 bodů, čáry velikosti 11; a 2- (56,11,2)).[14]
- Jsou známy dva dvojplošníky řádu 11 (a 79 bodů, čáry velikosti 13; a 2- (79,13,2)).[15]
Dvojplošníky objednávek 5, 6, 8 a 10 neexistují, jak ukazuje Věta Bruck-Ryser-Chowla.
Hadamard 2 vzory
An Hadamardova matice velikosti m je m × m matice H jejichž položky jsou ± 1 takové, že HH⊤ = mJám, kde H⊤ je transpozice H a Jám je m × m matice identity. Může být vložena Hadamardova matice standardizovaný formulář (tj. převedeno na ekvivalentní Hadamardovu matici), kde jsou položky prvního řádku a prvního sloupce všechny +1. Pokud velikost m > 2 pak m musí být násobkem 4.
Vzhledem k Hadamardově matici velikosti 4A ve standardizované formě odeberte první řádek a první sloupec a převádějte každé −1 na 0. Výsledná matice 0–1 M je matice výskytu symetrického 2- (4A − 1, 2A − 1, A - 1) design zvaný Hadamard 2-design.[16] Obsahuje bloky / body; každý obsahuje / je obsažen v body / bloky. Každá dvojice bodů je obsažena přesně bloky.
Tato konstrukce je reverzibilní a matici dopadu symetrického 2-designu s těmito parametry lze použít k vytvoření Hadamardovy matice velikosti 4A.
Vyřešitelné 2 vzory
A vyřešitelný 2-design je BIBD, jehož bloky lze rozdělit na sady (tzv paralelní třídy), z nichž každý tvoří oddíl bodové sady BIBD. Sada paralelních tříd se nazývá a rozlišení designu.
Pokud je 2- (proti,k, λ) rozlišitelný design má C paralelní třídy b ≥ proti + C − 1.[17]
V důsledku toho nemůže mít symetrický design netriviální (více než jednu paralelní třídu) rozlišení.[18]
Archetypické řešitelné 2 vzory jsou konečné afinní letadla. Řešení slavného 15 školačka problém je rozlišení 2- (15,3,1) designu.[19]
Obecné vyvážené vzory (t-dizajn)
Dáno jakékoli kladné celé číslo t, a t-design B je třída k-prvkové podmnožiny X, volala bloky, takže každý bod X v X se objeví přesně r bloky a všechny t- podmnožina prvků T se objeví v přesně λ blocích. Čísla proti (počet prvků X), b (počet bloků), k, r, λ a t jsou parametry designu. Design lze nazvat a t-(proti,k, λ) - design. Znovu určují tato čtyři čísla b a r a samotná čtyři čísla nelze zvolit libovolně. Rovnice jsou
kde λi je počet bloků, které obsahují libovolné i-prvková sada bodů a λt = λ.
Všimněte si, že a .
Teorém:[20] Žádný t-(proti,k, λ) -design is also an s-(proti,k, λs) - design pro všechny s s 1 ≤s ≤ t. (Všimněte si, že "hodnota lambda" se mění výše a závisí na s.)
Důsledkem této věty je, že každý t- design s t ≥ 2 je také 2-design.
A t-(proti,k, 1) -design se nazývá a Steinerův systém.
Termín blokový design samo o sobě obvykle znamená 2-design.
Odvozené a rozšiřitelné t-vzory
Nechat D = (X, B) porazit-(proti,k,λ) design a p bod X. The odvozený design Dp má nastavený bod X − {p} a jako blok nastavte všechny bloky z D které obsahují p s p odstraněny. Je to (t − 1)-(proti − 1, k − 1, λ) design. Upozorňujeme, že odvozené návrhy s ohledem na různé body nemusí být izomorfní. Design E se nazývá rozšíření z D -li E má bod p takový, že Ep je izomorfní s D; voláme D rozšiřitelný pokud má příponu.
Teorém:[21] Pokud t-(proti,k,λ) design má tedy příponu k + 1 rozdělí b(proti + 1).
Jediný rozšiřitelný projektivní roviny (symetrické 2- (n2 + n + 1, n + 1, 1) vzory) jsou návrhy objednávek 2 a 4.[22]
Každý design Hadamard 2 je rozšiřitelný (na Hadamard 3-design).[23]
Teorém:.[24]Li D, symetrické 2- (proti,k, λ) design, je rozšiřitelný, pak jeden z následujících platí:
- D je design 2 Hadamard,
- proti = (λ + 2) (λ2 + 4λ + 2), k = λ2 + 3λ + 1,
- proti = 495, k = 39, λ = 3.
Všimněte si, že projektivní rovina řádu dva je Hadamard 2-design; projektivní rovina řádu čtyři má parametry, které spadají v případě 2; jediné další známé symetrické 2-vzory s parametry v případě 2 jsou dvojplošníky řádu 9, ale žádný z nich není rozšiřitelný; a není znám žádný symetrický 2-design s parametry případu 3.[25]
Inverzní letadla
Návrh s parametry prodloužení o afinní letadlo, tj. 3- (n2 + 1, n + 1, 1) design, se nazývá konečný inverzní rovinanebo Möbiovy letadlo objednávkyn.
Je možné poskytnout geometrický popis některých inverzních rovin, skutečně všech známých inverzních rovin. An vejcovitý v PG (3,q) je sada q2 + 1 bod, žádné tři kolineární. Je možné ukázat, že každá rovina (která je nadrovinou, protože geometrická dimenze je 3) PG (3,q) se setkává s vejcem Ó buď v 1 nebo q + 1 bod. Rovinné části o velikosti q + 1 z Ó jsou bloky inverzní roviny řáduq. Jakákoli inverzní rovina vznikající tímto způsobem se nazývá jako vejce. Všechny známé inverzní roviny jsou vejčité.
Příkladem vejcovodu je eliptický quadric, množina nul kvadratické formy
- X1X2 + F(X3, X4),
kde f je neredukovatelný kvadratická forma ve dvou proměnných přes GF (q). [F(X,y) = X2 + xy + y2 například].
Li q je lichá síla 2, je znám jiný typ vejcovin - Suzuki – Prsa vejčitá.
Teorém. Nechat q být kladné celé číslo, alespoň 2. (a) Pokud q je liché, pak jakýkoli vejcovod je projektivně ekvivalentní eliptické kvadrice v projektivní geometrii PG (3,q); tak q je hlavní síla a existuje jedinečná inverzní rovina řádu jako vejce q. (Není však známo, zda existují jiné než vejce.) B) pokud q je tedy vyrovnaný q je síla 2 a jakákoli inverzní rovina řádu q je vejčitý (ale mohou existovat některé neznámé vajíčka).
Částečně vyvážené vzory (PBIBD)
An n-třída asociační schéma sestává z a soubor X velikosti proti společně s a rozdělit S z X × X do n + 1 binární vztahy, R.0, R.1, ..., R.n. Dvojice prvků ve vztahu Ri se říká, že jsou ith–spolupracovníci. Každý prvek X má ni ith spolupracovníci. Dále:
- a nazývá se Vztah identity.
- Definování , pokud R v S, pak R * v S
- Li , počet takhle a je konstanta záleží na i, j, k ale ne na konkrétní volbu X a y.
Schéma přidružení je komutativní -li pro všechny i, j a k. Většina autorů předpokládá tuto vlastnost.
A částečně vyvážený neúplný design bloku s n přidružené třídy (PBIBD (n)) je blokový design založený na a proti-set X s b blokuje každou velikost k a každý prvek se objeví v r bloky, takže existuje asociační schéma s n třídy definované na X kde, pokud prvky X a y jsou ith spolupracovníci, 1 ≤ i ≤ n, pak jsou spolu přesně v λi bloky.
PBIBD (n) určuje schéma přidružení, ale konverzace je nepravdivá.[26]
Příklad
Nechat A(3) být následujícím asociačním schématem se třemi přidruženými třídami v sadě X = {1,2,3,4,5,6}. (i,j) položka je s pokud prvky i a j jsou ve vztahu Rs.
1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|
1 | 0 | 1 | 1 | 2 | 3 | 3 |
2 | 1 | 0 | 1 | 3 | 2 | 3 |
3 | 1 | 1 | 0 | 3 | 3 | 2 |
4 | 2 | 3 | 3 | 0 | 1 | 1 |
5 | 3 | 2 | 3 | 1 | 0 | 1 |
6 | 3 | 3 | 2 | 1 | 1 | 0 |
Bloky PBIBD (3) založené na A(3) jsou:
124 | 134 | 235 | 456 |
125 | 136 | 236 | 456 |
Parametry tohoto PBIBD (3) jsou: proti = 6, b = 8, k = 3, r = 4 a λ1 = λ2 = 2 a λ3 = 1. Také pro asociační schéma, které máme n0 = n2 = 1 a n1 = n3 = 2.[27] Matice dopadu M je