In der kombinatorischen Mathematik ist ein Blockentwurf eine Gruppe zusammen mit einer Familie von Teilmengen (manchmal sind wiederholte Teilmengen zulässig), deren Mitglieder ausgewählt werden, um einige Eigenschaften zu erfüllen, die für eine bestimmte Person als nützlich erachtet werden Anwendung. Diese Anwendungen kommen aus vielen Bereichen, einschließlich experimentellen Designs, endlicher Geometrie, Softwaretests, Kryptographie und algebraischer Geometrie. Viele Variationen wurden untersucht, aber am intensivsten untersucht wurden die ausgeglichenen unvollständigen Blockentwürfe (BIBDs oder 2-Designs), die historisch mit statistischen Problemen beim Entwurf von Experimenten in Zusammenhang standen. [1][2]
Ein Blockentwurf in die alle Blöcke die gleiche Größe haben, heißt einheitlich . Die in diesem Artikel beschriebenen Designs sind alle einheitlich. Paarweise ausgeglichene Designs (PBDs) sind Beispiele für Blockdesigns, die nicht notwendigerweise einheitlich sind.
Definition eines BIBD (oder 2-Designs) [ edit
Gegeben einer endlichen Menge X (von Elementen, die Punkte genannt werden ) ) und ganze Zahlen k r λ ≥ 1, wir definieren ein 2-Design (oder BIBD steht für ausgeglichenes unvollständiges Blockdesign) B um eine Familie von k -Element-Subsets von X genannt Blöcke zu sein any x in X ist in r Blöcken enthalten, und jedes Paar unterschiedlicher Punkte x und y in X ist in λ Blöcken enthalten.
"Familie" in der obigen Definition kann durch "set" ersetzt werden, wenn wiederholte Blöcke nicht zulässig sind. Designs, in denen wiederholte Blöcke nicht zulässig sind, werden als einfach bezeichnet.
Hier v (Anzahl der Elemente von X Punkte genannt), b (Anzahl der Blöcke), k , r und λ sind die -Parameter des Entwurfs. (Um degenerierte Beispiele zu vermeiden, wird auch angenommen, dass v > k ), so dass kein Block alle Elemente des Satzes enthält. Dies ist die Bedeutung von "unvollständig" im Namen dieser Designs.) In einer Tabelle:
v Punkte, Anzahl der Elemente X b Anzahl der Blöcke r Anzahl von Blöcken, die einen bestimmten Punkt enthalten k Anzahl von Punkten in einem Block λ Anzahl von Blöcken, die zwei (oder allgemeiner t ) verschiedene Punkte enthalten
Das Design wird als (19459009) v k λ - Design oder a ( v b bezeichnet r k λ ) - Entwurf. Die Parameter sind nicht alle unabhängig. v k und λ bestimmen b und r und nicht alle Kombinationen von v ] k und λ sind möglich. Die beiden Grundgleichungen, die diese Parameter verbinden, sind
erhalten durch Zählen der Anzahl von Paaren ( B p ), wobei B ein Block ist und p ein Punkt in diesem Block ist, und
aus der Zählung der dreifachen erhalten (19459009] p q B ), wobei p und q sind unterschiedliche Punkte, und B ist ein Block, der beide enthält, und teilt diese Zählung durch v .
Diese Bedingungen sind nicht ausreichend, da beispielsweise kein (43,7,1) -Design existiert. [3]
Die -Ordnung von a 2 -design wird definiert als n = r - λ . Die Ergänzung eines 2-Designs wird erhalten, indem jeder Block durch seine Ergänzung in der Punktmenge X ersetzt wird. Es ist auch ein 2-Design und hat Parameter v ′ = v b ′ = b r
Ein fundamentaler Satz, Fisher's Ungleichheit, benannt nach dem Statistiker Ronald Fisher, lautet, dass b ≥ v in einem beliebigen 2-Design.
Beispiele [ edit ]
Das einzigartige (6,3,2) -Design hat 10 Blöcke ( b = 10), und jedes Element wird 5 wiederholt mal ( r = 5). [4] Unter Verwendung der Symbole 0 - 5 sind die Blöcke die folgenden Tripel:
- 012 013 024 035 045 125 134 145 234 235.
Eines von vier nicht-isomorphen (8,4,3) -Designs hat 14 Blöcke, wobei jedes Element 7 Mal wiederholt wird. Unter Verwendung der Symbole 0 - 7 sind die Blöcke die folgenden 4-Tupel: [4]
- 0123 0124 0156 0257 0345 0367 0467 1267 1346 1457 2357 2347 2356 2456.
Die einzigartigen (7, 3.1) -Design hat 7 Blöcke, wobei jedes Element dreimal wiederholt wird. Unter Verwendung der Symbole 0 - 6 sind die Blöcke die folgenden Tripel: [4]
- 013 026 045 124 156 235 346. Wenn die Elemente als Punkte auf einer Fano-Ebene gedacht sind, dann sind diese Blöcke the lines.
Symmetric BIBDs [ edit ]
Der Fall der Gleichheit in der Fisher-Ungleichung, dh ein 2-Design mit einer gleichen Anzahl von Punkten und Blöcken, wird als a bezeichnet symmetrisches Design . [5] Symmetrische Designs haben die kleinste Anzahl von Blöcken unter allen 2 Designs mit der gleichen Anzahl von Punkten.
In einem symmetrischen Entwurf r = k gilt ebenso wie b = v und obwohl dies im Allgemeinen nicht stimmt In willkürlichen 2-Designs treffen sich in einem symmetrischen Design alle zwei verschiedenen Blöcke in λ Punkten. [6] Ein Satz von Ryser liefert das Gegenteil. Wenn X ein v -Elementsatz ist und B ein v -Elementsatz von k - Element-Subsets (die "Blöcke"), so dass zwei verschiedene Blöcke genau λ-Punkte gemeinsam haben, dann ( X, B ) ist ein symmetrischer Blockentwurf. [7] 19659006] Die Parameter eines symmetrischen Designs erfüllen
Dies setzt starke Einschränkungen für v so dass Anzahl der Punkte ist alles andere als willkürlich. Der Bruck-Ryser-Chowla-Theorem gibt notwendige, aber nicht ausreichende Bedingungen für das Vorhandensein eines symmetrischen Entwurfs hinsichtlich dieser Parameter vor.
Das Folgende sind wichtige Beispiele für symmetrische 2-Designs:
Projektionsebenen [ edit ]
Endliche Projektionsebenen sind symmetrische 2-Konstruktionen mit λ = 1 und Ordnung n > 1. Für diese Designs wird die symmetrische Designgleichung:
Seit k = r können wir die -Ordnung einer projektiven Ebene schreiben. als n = k - 1 und aus der angezeigten Gleichung oben erhalten wir v = ( n + 1) n + 1 = n 2 + n + 1 Punkte in einer Projektionsebene der Ordnung n .
Da eine Projektionsebene ein symmetrisches Design ist, haben wir b = v was bedeutet, dass b = n 2 ist ] + n + 1 auch. Die Anzahl b ist die Anzahl der Zeilen der Projektionsebene. Da λ = 1 nicht wiederholt werden kann, kann es sich bei einer Projektionsebene um ein einfaches 2-Design handeln, bei dem die Anzahl der Linien und die Anzahl der Punkte immer gleich sind. Für eine Projektionsebene ist k die Anzahl der Punkte auf jeder Linie und ist gleich n +. In ähnlicher Weise r = n + 1 ist die Anzahl der Zeilen, mit denen ein bestimmter Punkt ein Ereignis ist.
Für n = 2 erhalten wir eine Projektionsebene der Ordnung 2, auch Fano-Ebene genannt, mit v = 4 + 2 + 1 = 7 Punkten und 7 Linien. In der Fano-Ebene hat jede Linie n + 1 = 3 Punkte und jeder Punkt gehört zu n + 1 = 3 Zeilen.
Es ist bekannt, dass projektive Ebenen für alle Ordnungen existieren, bei denen es sich um Primzahlen oder Primzahlen handelt. Sie bilden die einzige bekannte unendliche Familie (mit einem konstanten λ-Wert) von symmetrischen Blockdesigns. [8]
Doppeldecker [ edit
A Doppeldecker oder Doppeldeckergeometrie ist ein symmetrischer 2-Entwurf mit λ = 2; Das heißt, jeder Satz von zwei Punkten ist in zwei Blöcken ("Linien") enthalten, während sich zwei beliebige Linien in zwei Punkten schneiden. [8] Sie ähneln endlichen Projektionsebenen, außer dass zwei Punkte eine Linie bestimmen (und zwei Linien, die einen Punkt bestimmen), zwei Punkte bestimmen zwei Linien (Punkte). Eine Doppelebene der Ordnung n ist eine, deren Blöcke k = n + 2 Punkte haben; es hat v = 1 + ( n + 2) ( n + 1) / 2 Punkte (seit r = k ).
Die 18 bekannten Beispiele [9] sind nachstehend aufgeführt.
- (Trivial) Die Doppelebene der Ordnung 0 hat 2 Punkte (und Linien der Größe 2; ein 2- (2,2,2) -Design); Es handelt sich um zwei Punkte mit zwei Blöcken, die jeweils aus beiden Punkten bestehen. Geometrisch ist es das Digon.
- Die Doppelebene der Ordnung 1 hat 4 Punkte (und Linien der Größe 3; ein 2- (4,3,2) -Design); es ist das vollständige Design mit v = 4 und k = 3. Geometrisch gesehen sind die Punkte die Eckpunkte und die Blöcke die Gesichter eines Tetraeders.
- Die Doppelebene der Ordnung 2 ist das Komplement der Fano-Ebene: Es hat 7 Punkte (und Linien der Größe 4; ein 2- (7,4,2)), wobei die Linien als Komplemente der (3- Linien in der Fano-Ebene [10]
- Die Doppelebene der Ordnung 3 hat 11 Punkte (und Linien der Größe 5; eine 2- (11,5,2)) und ist auch bekannt als Paley-Doppeldecker nach Raymond Paley; es ist dem Paley-Digraphen der Ordnung 11 zugeordnet, der aus dem Feld mit 11 Elementen aufgebaut ist, und ist das Hadamard 2-Design, das der Hadamard-Matrix der Größe 12 zugeordnet ist. siehe Paley-Konstruktion I.
- Algebraisch entspricht dies der außergewöhnlichen Einbettung der projektiven speziellen linearen Gruppe PSL (2,5) in PSL (2,11) - siehe projektive Linie Gruppe: Aktion am p Punkte für Details. [11]
- Es gibt drei Doppelebenen der Ordnung 4 (und 16 Punkte, Linien der Größe 6; ein 2- (16,6,2,2)). Eine davon ist die Kummer-Konfiguration. Diese drei Entwürfe sind ebenfalls Menons Entwürfe.
- Es gibt vier Doppelebenen der Ordnung 7 (und 37 Punkte, Linien der Größe 9; a 2- (37,9,2)). [12] [19659111] Es gibt fünf Doppeldecker der Ordnung 9 (und 56 Punkte, Linien der Größe 11; a 2- (56,11,2)). [13]
- Zwei Doppeldecker der Ordnung 11 sind bekannt (und 79 Punkte, Linien der Größe 13; a 2- (79,13,2)). [14]
Doppelebenen der Ordnungen 5, 6, 8 und 10 existieren nicht, wie der Satz von Bruck-Ryser-Chowla zeigt.
Hadamard 2-designs [ edit ]
Eine Hadamard-Matrix der Größe m ist m
Bei einer Hadamard-Matrix der Größe 4 a in standardisierter Form entfernen Sie die erste Zeile und die erste Spalte und konvertieren alle -1 in eine 0. Die resultierende 0–1-Matrix M ist die Inzidenzmatrix eines symmetrischen 2- (4 a - 1, 2 a - 1, a - 1) Entwurfs, [Hadamard2 genannt -design . [15] Es enthält Blöcke / Punkte; jedes enthält / ist enthalten in Punkten / Blöcken. Jedes Punktepaar ist genau in enthalten.
Diese Konstruktion ist reversibel, und die Inzidenzmatrix eines symmetrischen 2-Designs mit diesen Parametern kann zur Bildung einer Hadamard-Matrix der Größe 4 verwendet werden a .
Resolvable 2-designs [ edit ]
Ein auflösbares 2-Design ist eine BIBD, deren Blöcke in parallele Klassen (19459009) unterteilt werden können ), die jeweils eine Aufteilung der Punktmenge des BIBD bilden. Die Menge der parallelen Klassen wird als Resolution des Designs bezeichnet.
Wenn ein 2 - ( v k λ) auflösbares Design c parallele Klassen hat, dann b ≥ ] v + c - 1. [16]
Folglich kann eine symmetrische Konstruktion keine nicht triviale (mehr als eine parallele Klasse) Auflösung haben. [17]
Archetypisch auflösbare 2-Entwürfe sind die endlichen affinen Ebenen. Eine Lösung des berühmten 15-Schüler-Problems ist eine Lösung eines 2- (15,3,1) -Designs. [18]
Generalisierung: t -designs [ edit
In Anbetracht einer beliebigen positiven Zahl t t -Design B ist eine Klasse von k -Einsätzen von X genannt Blöcke so dass jeder Punkt x in X genau in r und erscheint. t -Element-Teilmenge T erscheint in genau λ-Blöcken. Die Zahlen v (die Anzahl der Elemente von X ), b (die Anzahl der Blöcke), k
wobei λ i ist die Anzahl der Blöcke, die einen beliebigen Satz von i -Elementen enthalten.
Man beachte, dass .
Satz : [19] Jedes t - ( v k λ) - Design ist auch ein s - ( v k λ s ) - Entwurf für alle s mit 1 ≤ s ≤ t . (Beachten Sie, dass sich der "Lambda-Wert" wie oben ändert und von s abhängt.)
Eine Folge dieses Satzes ist, dass jedes t -Design mit t ≥ 2 auch ein 2-Design ist.
A t - ( v k 1) - Design wird als Steinersystem bezeichnet.
Der Begriff Blockdesign bedeutet an sich normalerweise ein 2-Design.
Abgeleitete und erweiterbare t-designs [ edit ]
. Lassen Sie D = ( X
Satz : [20] Wenn ein t - ( v k
Die einzigen erweiterbaren projektiven Ebenen (symmetrisch 2 - ( n 2 + n + 1, n + 1, 1) sind) die der Ordnungen 2 und 4. [21]
Jedes Hadamard 2-Design ist erweiterbar (auf ein Hadamard 3-Design ). [22]
Satz : [23] Wenn D ein symmetrisches 2 - ( v k λ) Design ist erweiterbar, dann gilt einer der folgenden Punkte:
- D ist ein Hadamard-2-Design,
- v = (λ + 2) (λ 2 + 4λ + 2), k = λ 2 + 3λ + 1,
- v = 495, k = 39, λ = 3.
Beachten Sie, dass das Projektiv Die zweite Ebene ist ein Hadamard-2-Design. die Projektionsebene der Ordnung vier hat Parameter, die in Fall 2 fallen; Die einzigen anderen bekannten symmetrischen 2-Designs mit Parametern in Fall 2 sind die Doppelebenen der Ordnung 9, aber keine davon ist erweiterbar. und es ist kein symmetrisches 2-Design mit den Parametern von Fall 3 bekannt. [24]
Inversive Ebenen [ edit ]
Ein Design mit den Parametern der Ausdehnung einer affinen Ebene, dh , a 3 - ( n 2 + 1, n + 1, 1), wird als endliche inversive Ebene oder Möbius-Ebene bezeichnet. n .
Es ist möglich, einige inversive Ebenen, und zwar alle bekannten inversiven Ebenen, geometrisch zu beschreiben. Ein Ovoid in PG (3, q ) ist ein Satz von q 2 + 1 Punkte, keine drei Kollineare. Es kann gezeigt werden, dass jede Ebene (die eine Hyperebene ist, da die geometrische Dimension 3 ist) von PG (3, q ) in 1 oder q einem Ovoid O entspricht + 1 Punkte. Die ebenen Schnitte der Größe q + 1 von O sind die Blöcke einer inversiven Ordnungsebene q . Jede inversive Ebene, die auf diese Weise entsteht, wird als egglike bezeichnet. Alle bekannten inversen Ebenen sind egglic.
Ein Beispiel für ein Ovoid ist das elliptische Quadrat, die Menge der Nullen der quadratischen Form
-
-
- x 1 x 2 + f
- [
- x [19599949] 3 x 4 ),
- [
- x 1 x 2 + f
-
wobei f eine irreduzible quadratische Form in zwei Variablen über GF ( q ist ). f ( x y ) = x 2 + xy
Wenn q eine ungerade Potenz von 2 ist, ist eine andere Art von Ovoid bekannt - das Suzuki-Tits-Ovoid.
Theorem . Sei q eine positive ganze Zahl, mindestens 2. (a) Wenn q ungerade ist, dann ist jedes Ovoid dem elliptischen Quadric in einer projektiven Geometrie PG (3, q ); so ist q eine Prim-Power, und es gibt eine einzigartige egglike inverse Ebene der Ordnung q . (Es ist jedoch nicht bekannt, ob nicht-egglike existieren.) (B) Wenn q gerade ist, dann q ist eine Potenz von 2 und jede inverse Ebene der Ordnung q ist egglisch (es können jedoch einige unbekannte Ovoiden vorhanden sein).
Teilabgeglichene Designs (PBIBDs) [ edit ]
Ein n -Klasse-Assoziationsschema besteht aus einer Gruppe X X v zusammen mit einer Trennwand S von X × X in n + 1 binäre Beziehungen, R R 1 ..., R n . Ein Paar Elemente in Beziehung R i wird als i th- Associates bezeichnet. Jedes Element von X hatte n i i i. Mitarbeiter. Außerdem:
- und wird als Identitätsbeziehung bezeichnet.
- Definition wenn R in S dann R * in S
- If )
[1945 R i { displaystyle (x, z) in R_ {i}} und Rj { displaystyle (z, y) in R_ {j}} ist eine Konstante in Abhängigkeit von i- j k jedoch nicht nach der besonderen Wahl von x und y .
![(x, y) in R_ {k} [19659216]die Anzahl von <span class=](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9a59e49b8c4cfa69f8105f023dc5493ba32ac63)
![z in X [196593] [196593] ] x </mi><mo></mo><mi> z </mi><mo stretchy=](https://wikimedia.org/api/rest_v1/media/math/render/svg/dff47a41328065a0e15e3a7089cfd392ee954e36)
) 
und 
ist eine Konstante 
Ein Assoziationsschema ist kommutativ p
Ein teilweise ausgeglichenes unvollständiges Blockdesign mit n assoziierten Klassen (PBIBD ( n )) ist ein Blockdesign, das auf einem v
Ein PBIBD ( n ) bestimmt ein Assoziationsschema, aber das Gegenteil ist falsch. [25]
Beispiel [ edit
Es sei A ] (3) sei das folgende Assoziationsschema mit drei assoziierten Klassen am Set X = {1,2,3,4,5,6}. Der Eintrag [ i j ] lautet s wenn Elemente i und j im Verhältnis R Die Blöcke von PBIBD (3), die auf A (3) basieren, sind: Die Parameter dieser PBIBD (3) sind: v = 6, b = 8, k = 3, r = 4 und λ 1 = λ 2 = 2 und λ 3 = 1. Außerdem haben wir für das Assoziationsschema n 0 = n 2 = 1 und n 1 = n 3 = 2. [26] Die Parameter einer PBIBD ( m ) erfüllen: [27] Eine PBIBD (1) ist eine BIBD und eine PBIBD (2), in der λ 1 = λ2 is a BIBD.[28] PBIBD(2)s have been studied the most since they are the simplest and most useful of the PBIBDs.[29] They fall into six types[30] based on a classification of the then known PBIBD(2)s by Bose & Shimamoto (1952 ):[31] The mathematical subject of block designs originated in the statistical framework of design of experiments. These designs were especially useful in applications of the technique of analysis of variance (ANOVA). This remains a significant area for the use of block designs. While the origins of the subject are grounded in biological applications (as is some of the existing terminology), the designs are used in many applications where systematic comparisons are being made, such as in software testing. The incidence matrix of block designs provide a natural source of interesting block codes that are used as error correcting codes. The rows of their incidence matrices are also used as the symbols in a form of pulse-position modulation.[32] Suppose that skin cancer researchers want to test three different sunscreens. They coat two different sunscreens on the upper sides of the hands of a test person. After a UV radiation they record the skin irritation in terms of sunburn. The number of treatments is 3 (sunscreens) and the block size is 2 (hands per person). A corresponding BIBD can be generated by the R-function design.bib of the R-package agricolae and is specified in the following table: The investigator chooses the parameters v = 3k = 2 and λ = 1 for the block design which are then inserted into the R-function. Subsequently, the remaining parameters b and r are determined automatically. Using the basic relations we calculate that we need b = 3 blocks, that is, 3 test people in order to obtain a balanced incomplete block design. Labeling the blocks AB and Cto avoid confusion, we have the block design, A corresponding incidence matrix is specified in the following table: Each treatment occurs in 2 blocks, so r = 2. Just one block (C) contains the treatments 1 and 2 simultaneously and the same applies to the pairs of treatments (1,3) and (2,3). Therefore, λ = 1. It is impossible to use a complete design (all treatments in each block) in this example because there are 3 sunscreens to test, but only 2 hands on each person. 19659368] 1 2 3 4 5 6 1 0 1 1 2 3 3 2 1 0 0 719659379] ] 2 3 3 1 1 0 3 3 2 4 2 2 19659399] 0 1 1 5 3 2 3 1 0 1 1 1 1 1 1 ] 3 2 1 1 0 124 134 235 456 125 136 236 456 Eigenschaften Eigenschaften edit ]
Two associate class PBIBDs[edit]
Applications[edit]
Statistical application[edit]
Plots Block Treatment 101 1 3 102 1 2 201 2 1 202 2 3 301 3 2 302 3 1 Treatment Block A Block B Block C 1 0 1 1 2 1 0 1 3 1 1 0 See also[edit]
References[edit]
External links[edit]
![sum _ {i = 1} ^ {m} n_ {i} = v-1 [1965] 9216] </li> <li> <span class=](https://wikimedia.org/api/rest_v1/media/math/render/svg/09d98937a7b1eed2563ad7a40f175b153f03a53c)
No comments:
Post a Comment