Symmetrischer Blockplan

Unterklasse eines Blockplans
(Weitergeleitet von Hadamard-Blockplan)

Ein symmetrischer Blockplan (auch symmetrisches Blockdesign genannt) ist in der endlichen Geometrie und der Kombinatorik ein Blockplan und damit eine endliche Inzidenzstruktur, bei dem die Anzahl der Blöcke gleich der Anzahl der Punkte ist.[1] Symmetrische Blockpläne werden beispielsweise bei der Versuchsplanung oder zur Konstruktion von Codes verwendet. Ein symmetrischer Blockplan ist durch eine quadratische (v×v)-Matrix darstellbar, die so mit Nullen und Einsen gefüllt sind, dass die folgenden beiden Bedingungen erfüllt sind:

  • Die Anzahl k der Einsen ist in jeder Zeile und Spalte gleich.
  • Je zwei Zeilen und je zwei Spalten haben eine Anzahl λ an Einsen gemeinsam.

Die Zeilen dieser Matrix bezeichnen die Blöcke und die Spalten die Punkte der zugrunde liegenden Inzidenzstruktur.

Obwohl ihre Eigenschaften leicht verständlich sind, sind solche symmetrischen Blockpläne nicht beliebig konstruierbar und existieren nur für gewisse Kombinationen der Parameter v, k und λ. Die Existenz vieler symmetrischer Blockpläne ist daher noch nicht geklärt. Der Nachweis der Nichtexistenz eines bestimmten symmetrischen Blockplans (der projektiven Ebene der Ordnung 10 bzw. des symmetrischen (111,11,1)-Blockplans) mit Hilfe eines Computerbeweises sorgte daher im Jahr 1991 für großes Interesse.[2]

Definitionen Bearbeiten

Sei B ein 2-(v,k,λ)-Blockplan. Ferner seien für B diese Bedingungen erfüllt:

  • B enthält genau v Blöcke
  • B enthält genau v Punkte
  • jeder Punkt von B liegt auf genau k Blöcken
  • jeder Block von B geht durch genau k Punkte
  • je zwei verschiedene Blöcke von B schneiden sich in genau λ Punkten
  • je zwei verschiedene Punkte von B sind durch genau λ Blöcke verbunden

Dann bezeichnet man B als einen symmetrischen 2-(v,k,λ)-Blockplan oder auch kurz als (v,k,λ)-Blockplan.

Als Ordnung n eines symmetrischen (v,k,λ)-Blockplans bezeichnet man die Differenz n = k - λ.

Eine nichtleere Punktmenge eines symmetrischen Blockplans mit der Eigenschaft, dass keine drei Punkte dieser Menge in einem Block enthalten sind, nennt man Oval. Damit verbunden ist eine disjunkte Unterteilung der Blöcke des Blockplans in:

  • Sekanten (Blöcke, welche genau zwei Punkte des Ovals enthalten)
  • Tangenten (Blöcke, welche genau einen Punkt des Ovals enthalten)
  • Passanten (Blöcke, welche keine Punkte des Ovals enthalten)

Die Anzahl der Punkte eines Ovals bezeichnet man als die Ordnung des Ovals.

Veranschaulichung Bearbeiten

Definitionsgemäß kann der (v,k,λ)-Blockplan durch eine Inzidenzmatrix mit v Zeilen und v Spalten repräsentiert werden, welche in jeder Zeile und in jeder Spalte genau k Einsen enthält (die restlichen Einträge sind Nullen) und bei welcher das Skalarprodukt von je zwei Zeilen ebenso wie das von je zwei Spalten genau λ beträgt (d. h. je zwei Zeilen bzw. je zwei Spalten haben an genau λ Stellen eine Eins gemeinsam). Hier ist z. B. eine anschauliche Darstellung der Inzidenzmatrix des (7,3,1)-Blockplans, wobei die Einsen durch Kreise und die Nullen durch Punkte dargestellt sind, um die Struktur besser erkennen zu können:

O O O . . . .   diese Zeile repräsentiert den ersten Block. Er enthält die Punkte 1, 2 und 3
O . . O O . .
O . . . . O O
. O . O . O .   diese Zeile repräsentiert den vierten Block. Er enthält die Punkte 2, 4 und 6
. O . . O . O   diese Zeile repräsentiert den fünften Block. Er schneidet den vierten Block im Punkt 2
. . O O . . O
. . O . O O .
         
         Diese Spalte repräsentiert den Punkt 6. Er liegt auf den Blöcken 3, 4 und 7 
  
  Diese Spalte repräsentiert den Punkt 2. Er ist mit dem Punkt 6 durch den Block 4 verbunden 

Alternativ kann der Blockplan auch durch das Auflisten seiner Blöcke dargestellt werden, wobei man pro Block in einer Zeile die in ihm enthaltenen Punkte aufschreibt. Hier wieder das Beispiel für den (7,3,1)-Blockplan:

  1   2   3   diese Zeile repräsentiert den ersten Block. Er enthält die Punkte 1, 2 und 3
  1   4   5
  1   6   7
  2   4   6   diese Zeile repräsentiert den vierten Block. Er enthält die Punkte 2, 4 und 6
  2   5   7   diese Zeile repräsentiert den fünften Block. Er schneidet den vierten Block im Punkt 2
  3   4   7
  3   5   6

Existenzbedingungen Bearbeiten

Eine zentrale Fragestellung ist, welche symmetrischen (v,k,λ)-Blockpläne überhaupt existieren. Es gibt eine Reihe von notwendigen Kriterien für die Existenz von Blockplänen, mit denen man viele Parameterkombinationen ausschließen kann. Solche Kriterien liefern zum Beispiel die verallgemeinerte Fisher-Ungleichung (auch Satz von Ray-Chaudhuri-Wilson genannt) und der Satz von Bruck-Ryser-Chowla. Zwei leicht zu prüfende notwendige Bedingungen für die Existenz eines (v,k,λ)-Blockplans sind:

Erfüllt ein Parametertripel v,k,λ auch nur eine dieser Bedingungen nicht, so existiert auch kein (v,k,λ)-Blockplan. Dagegen sind diese Bedingungen nicht hinreichend: selbst wenn sie erfüllt sind, muss der (v,k,λ)-Blockplan nicht existieren.

Klassifizierung Bearbeiten

Die symmetrischen Blockpläne können anhand ihrer Parameter v,k,λ in Kategorien eingeteilt werden. Nachfolgend sind die vier wichtigsten aufgeführt:

Projektive Ebene Bearbeiten

Alle symmetrischen Blockpläne mit   heißen projektive Ebenen. Ihre Parameter sind

 ,

mit   als Ordnung der projektiven Ebene. Ist diese Ordnung   eine Primzahl oder eine Potenz einer Primzahl, so existiert auch die zugehörige projektive Ebene mit dieser Ordnung.[3] In keinem anderen Fall dagegen ist bis jetzt die Existenz einer projektiven Ebene bekannt. Für die beiden kleinsten Fälle dieser Art (n = 2·3 und n = 2·5) ist die Existenz bereits widerlegt. Es existiert damit weder ein (43,7,1)-Blockplan (dies wäre die projektive Ebene der Ordnung 6) noch ein (111,11,1)-Blockplan (dies wäre die seit langem vergeblich gesuchte projektive Ebene der Ordnung 10). Die kleinste Ordnung, zu welcher die Existenz einer projektiven Ebene noch nicht geklärt ist, ist n = 12; der zugehörige Blockplan hat die Parameter (157,13,1).

Biplane Bearbeiten

Alle symmetrischen Blockpläne mit   heißen Biplanes, ihre Parameter sind

 ,

mit   als Ordnung der Biplane. Es sind bislang nur Biplanes der Ordnung n = 3, 4, 7, 9 und 11 bekannt.[4]

Triplane Bearbeiten

Alle symmetrischen Blockpläne mit   heißen Triplanes. Sie haben die Parameter

 ,

mit   als Ordnung der Triplane. Es sind bislang nur Triplanes der Ordnung n = 4, 6, 7, 9 und 12 bekannt.[5]

Hadamard-Blockplan Bearbeiten

Jeder symmetrische  -Blockplan wird als Hadamard-Blockplan (genauer: Hadamard-2-Blockplan) bezeichnet.[6] Der Name kommt daher, dass jeder normalisierten   - Hadamard-Matrix   ein solcher Blockplan zugeordnet werden kann und umgekehrt.[7] Dabei werden die erste Zeile und die erste Spalte der Hadamard-Matrix H, die aufgrund der Normalisierung nur Einträge 1 enthalten, gestrichen. Die verbleibende Matrix (mit den Einträgen 1 bzw. −1) wird als Inzidenzstruktur des Hadamard-Blockplanes verwendet (indem man die Einträge −1 als 0 interpretiert).

Alle Hadamard-2-Blockpläne sind symmetrische Blockpläne. Sie lassen sich zu Hadamard-3-Blockplänen erweitern (diese gehören allerdings nicht mehr zu den symmetrischen Blockplänen). Es gilt:

Jeder Hadamard- -Blockplan   lässt sich zu einem  -Blockplan   erweitern.[8] Die Erweiterung sieht so aus: Man vereinbart   mit einem zusätzlichen Punkt   als neue Punktmenge und   als neue Blockmenge für  .[9] Dann ist   der 3-Blockplan. Diese Erweiterung ist bis auf Isomorphie die einzig mögliche Erweiterung für den Hadamard-2-Blockplan  , so dass   für einen Punkt x in der Punktmenge von   gilt und   ein 3-Blockplan ist.   ist die Ableitung von   am Punkt x. Jeder  -Blockplan   hat für   als Ableitung an jedem Punkt einen Hadamard-2-Blockplan.[10] Ein 3-Blockplan ist genau dann stark auflösbar, wenn er ein Hadamard-3-Blockplan ist.

Übersicht über die kleinsten symmetrischen Blockpläne Bearbeiten

In der nachfolgenden Tabelle sind die Blockpläne nach λ und nach n - λ aufgelistet. Durch die Abgrenzung n - λ >= 1 wird hier zwar vordergründig eine Einschränkung vorgenommen. Sie ist jedoch äquivalent mit k <= v / 2, was bedeutet, dass jeder Block höchstens die Hälfte aller Punkte beinhalten darf. Die dazu komplementären Blockpläne (k > v / 2) sind hier nicht aufgeführt. Sie entstehen aus den hier aufgelisteten Blockplänen durch Vertauschung von 0 und 1 in den Inzidenzmatrizen, ihre Parameter sind (v,v-k,v-2k+λ).

Sofern die notwendige Bedingung λ(v-1) = k(k-1) sowie der Satz von Bruck-Ryser-Chowla erfüllt ist, enthält das entsprechende Tabellenelement die Bezeichnung (v,k,λ) des Blockplans, ansonsten bleibt die entsprechende Zelle leer, weil in diesem Fall kein Blockplan existieren kann. Grün gefärbte Zellen bedeuten, dass der entsprechende Blockplan existiert, und verlinken auf die explizite Darstellung des Blockplans. Rot gefärbte Zellen bedeuten, dass der entsprechende Blockplan nicht existiert. Bei gelb gefärbten Zellen ist die Existenz des Blockplans noch ungewiss.

In der Zeile λ = 1 stehen die projektiven Ebenen, in der Zeile λ = 2 die Biplanes, in der Zeile λ = 3 die Triplanes und in der Spalte n - λ = 1 die Hadamard-Blockpläne. Der kleinste Hadamard-Blockplan mit den Parametern (7,3,1) ist zugleich die projektive Ebene der Ordnung 2, der nächste mit den Parametern (11,5,2) ist zugleich die Biplane der Ordnung 3 und der (15,7,3) - Hadamard-Blockplan ist zugleich die Triplane der Ordnung 4.

n - λ
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
λ
1
(7,3,1) (13,4,1) (21,5,1) (31,6,1) (43,7,1) (57,8,1) (73,9,1) (91,10,1) (111,11,1) (133,12,1) (157,13,1) (183,14,1) (211,15,1) (241,16,1) (273,17,1) (307,18,1)
2 (11,5,2) (16,6,2) (29,8,2) (37,9,2) (56,11,2) (67,12,2) (79,13,2) (121,16,2) (137,17,2) (154,18,2) (191,20,2)
3 (15,7,3) (25,9,3) (31,10,3) (45,12,3) (71,15,3) (81,16,3) (115,19,3) (155,22,3)
4 (19,9,4) (40,13,4) (61,16,4) (69,17,4) (96,20,4) (139,24,4)
5 (23,11,5) (49,16,5) (85,21,5) (121,25,5) (131,26,5)
6 (27,13,6) (36,15,6) (41,16,6) (71,21,6) (78,22,6) (101,25,6) (127,28,6)
7 (31,15,7) (109,28,7)
8 (35,17,8) (70,24,8)
9 (39,19,9) (79,27,9) (85,28,9)
10 (43,21,10) (61,25,10) (66,26,10) (120,35,10) (127,36,10)
11 (47,23,11) (97,33,11) (103,34,11)
12 (51,25,12) (64,28,12) (112,37,12) (131,40,12)
13 (55,27,13) (121,40,13)
14 (59,29,14)
15 (63,31,15) (85,36,15) (105,40,15) (139,46,15)
16 (67,33,16)

Charakterisierung symmetrischer Blockpläne Bearbeiten

Wenn es zu einem symmetrischen (v,k,λ)-Blockplan mehrere nichtisomorphe Lösungen gibt, stellt sich die Frage, wie diese voneinander unterschieden werden können. Eine Möglichkeit ist die Suche nach speziellen Eigenschaften des Blockplans, welche unter Isomorphie invariant sind. Das bedeutet, dass diese Eigenschaft nach Durchführung beliebiger Zeilen- oder Spaltenpermutationen an der Inzidenzmatrix des Blockplans erhalten bleibt. Unterscheiden sich zwei Blockpläne in dieser Eigenschaft, handelt es sich um nichtisomorphe Lösungen. Der Umkehrschluss gilt dagegen nicht: zwei Blockpläne, welche sich in dieser Eigenschaft nicht unterscheiden, können isomorph sein oder nicht.

Ovale Bearbeiten

Die Anzahl der Ovale maximaler Ordnung eines Blockplans ist eine solche Invariante. Besitzen zwei Lösungen eines Blockplans unterschiedlich viele Ovale gleicher Ordnung oder besitzt ein Blockplan Ovale größerer Ordnung als der andere, so sind diese Blockpläne nichtisomorph.

Beispiel: Es existieren genau drei nichtisomorphe Lösungen des (16,6,2)-Blockplans. Alle drei besitzen Ovale der Ordnung 4, jedoch in unterschiedlicher Anzahl:
  • Lösung 1 enthält 60 Ovale der Ordnung 4
  • Lösung 2 enthält 28 Ovale der Ordnung 4
  • Lösung 3 enthält 12 Ovale der Ordnung 4
Damit sind diese drei Lösungen paarweise nichtisomorph.

λ-chains Bearbeiten

Für Biplanes (symmetrische Blockpläne mit λ=2) können λ-chains[11] als Unterscheidungsmerkmal herangezogen werden.

Man wählt einen Block der Biplane und nennt ihn Indexblock. Jeder andere Block der Biplane kann durch das Punktepaar gekennzeichnet werden, welches dieser Block mit dem Indexblock gemeinsam hat. Nun korrespondiert jeder Punkt P der Biplane, welcher nicht auf dem Indexblock liegt, mit einer Permutation der Punkte des Indexblocks. In dieser Permutation sind zwei Punkte genau dann benachbart, wenn ein Block, der den Punkt P enthält, durch genau dieses Punktpaar gekennzeichnet ist. Die sich ergebenden Permutations-Zyklen nennt man λ-chains. Man führt diese Berechnung für jeden Indexblock und jeden nicht damit inzidenten Punkt durch und zählt die sich dabei ergebenden Zyklen-Längen. Die λ-chains werden in der Form   mit den Anzahlen   und den Zyklenlängen   dargestellt.

Beispiel: In diesem (16,6,2)-Blockplan ist ein Block als Indexblock markiert sowie jeder Punkt '9'. Die zusammengesetzten Kennzeichnungs-Punktpaare ergeben den Zyklus (2,7,12,6,15,8). Damit hat dieser λ-chain die Länge 6.
Blöcke Kennzeichnung
1 2 3 5 10 15 2 15
2 3 4 6 11 16 2 6
3 4 5 7 9 12 7 12
4 5 6 8 10 13 6 8
1 5 6 7 11 14 6 7
2 6 7 8 12 15 Indexblock
1 3 7 8 13 16 7 8
1 2 4 8 9 14 2 8
2 7 9 10 11 13 2 7
3 8 10 11 12 14 8 12
1 4 11 12 13 15 12 15
2 5 12 13 14 16 2 12
3 6 9 13 14 15 6 15
4 7 10 14 15 16 7 15
5 8 9 11 15 16 8 15
1 6 9 10 12 16 6 12
Die drei nichtisomorphen Lösungen des (16,6,2)-Blockplans haben diese λ-chains:
  • Lösung 1 hat die λ-chains 320*3 (d. h. 320 λ-chains der Länge 3)
  • Lösung 2 hat die λ-chains 192*3, 64*6 (d. h. 192 λ-chains der Länge 3 und 64 λ-chains der Länge 6)
  • Lösung 3 hat die λ-chains 128*3, 96*6 (d. h. 128 λ-chains der Länge 3 und 96 λ-chains der Länge 6)
Damit sind diese drei Lösungen paarweise nichtisomorph.

Signatur Bearbeiten

Eine in vielen Fällen sehr wirkungsvolle Unterscheidungshilfe ist die Erstellung einer Signatur. Hierzu werden vier verschiedene Blöcke markiert: ein Indexblock   sowie drei weitere Blöcke  . Sei   die Anzahl aller Punkte, welche mit mehr als einem der insgesamt 4 Blöcke inzidiert. Sei   die Häufigkeit des kleinsten  , wenn   alle   möglichen Kombinationen durchlaufen. Durchläuft nun auch der Indexblock   sämtliche   Möglichkeiten, so wird die Signatur in der Form   mit den Anzahlen   und den ermittelten   dargestellt.

Sofern es zur eindeutigen Unterscheidung notwendig ist, wird neben dem kleinsten   auch noch der nächstgrößere Wert in die Erstellung der Signatur aufgenommen. Dann wird sie in der Form   dargestellt.

Beispiel: In diesem (16,6,2)-Blockplan sind ein Indexblock   sowie drei Blöcke   markiert:
Blöcke
1 2 3 5 10 15
2 3 4 6 11 16 Block A
3 4 5 7 9 12
4 5 6 8 10 13
1 5 6 7 11 14
2 6 7 8 12 15 Indexblock I
1 3 7 8 13 16
1 2 4 8 9 14
2 7 9 10 11 13
3 8 10 11 12 14
1 4 11 12 13 15 Block B
2 5 12 13 14 16 Block C
3 6 9 13 14 15
4 7 10 14 15 16
5 8 9 11 15 16
1 6 9 10 12 16
Bei dieser Konstellation kommen die Punkte 2,4,6,11,12,13,15 und 16 in mehr als einem der vier Blöcke vor. Daher ist hier   = 8. Durchläuft man mit den Blöcken   alle   möglichen Kombinationen, erhält man für   folgende Häufigkeiten: 12*4, 32*6, 60*7, 312*8, 32*10, 7*12. Damit ist   = 12. Lässt man nun noch den Indexblock über alle 16 Blöcke laufen, erhält man in diesem Beispiel jedes Mal den gleichen Wert für   und die Signatur lautet somit 16*12.
Die drei nichtisomorphen Lösungen des (16,6,2)-Blockplans haben diese Signaturen:
  • Lösung 1 hat die Signatur 16*20
  • Lösung 2 hat die Signatur 16*12
  • Lösung 3 hat die Signatur 16*8
Damit sind diese drei Lösungen paarweise nichtisomorph.

Literatur Bearbeiten

Einzelnachweise und Anmerkungen Bearbeiten

  1. Beutelspacher, S. 43
  2. Clement W. H. Lam: The Search for a Finite Projective Plane of Order 10. In: The American Mathematical Monthly, vol. 98, 1991, S. 305–318
  3. Beth, Jungnickel, Lenz: 2.3
  4. Beth, Jungnickel, Lenz (1986, 1999), Appendex-Table B
  5. Sanja Rukavina: Some new triplanes of order twelve. Glas. Mat. Vol 36 (2001) 105-125
  6. Beth, Jungnickel, Lenz (1986, 1999), I.9 Hadamard designs
  7. Beth, Jungnickel, Lenz (1986, 1999), Lemma I.9.3
  8. Beth, Jungnickel, Lenz (1986, 1999), Theorem I.9.9
  9. Die Blöcke von   können als Mengen von Punkten aufgefasst werden, da Hadamard-Blockpläne einfach sind.
  10. Beth, Jungnickel, Lenz (1986, 1999), Theorem II.8.10, Corollary II.8.11
  11. Chester J. Salwach, Joseph A. Mezzaroba: The four known biplanes with k = 11. In: Internat. J. Math. & Math. Sci., Vol. 2 No. 2, 1979, S. 253