Symmetrischer 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. 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.

Definitionen

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

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

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:

$\lambda \cdot (v-1)=k\cdot (k-1)$ , wie im Artikel Blockplan hergeleitet
k - λ ist eine Quadratzahl, falls v gerade ist (Satz von Schützenberger; gilt auch nach dem Satz von Bruck-Ryser-Chowla)

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

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

Projektive Ebene

→ Hauptartikel: Projektive Ebene

Alle symmetrischen Blockpläne mit $\lambda = 1$ heißen projektive Ebenen. Ihre Parameter sind

$(v,k,\lambda )=\left(n^{2}+n+1,n+1,1\right)$ ,

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. 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

Alle symmetrischen Blockpläne mit $\lambda = 2$ heißen Biplanes, ihre Parameter sind

$(v,k,\lambda )=\left({\frac {n^{2}+3n+4}2},n+2,2\right)$ ,

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

Triplane

Alle symmetrischen Blockpläne mit $\lambda =3$ heißen Triplanes. Sie haben die Parameter

$(v,k,\lambda )=\left({\frac {n^{2}+5n+9}{3}},n+3,3\right)$ ,

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

Hadamard-Blockplan

Jeder symmetrische $2{\text{-}}(4n-1,2n-1,n-1)$ -Blockplan wird als Hadamard-Blockplan (genauer: Hadamard-2-Blockplan) bezeichnet. Der Name kommt daher, dass jeder normalisierten $4n\times 4n$ - Hadamard-Matrix $(n\geq 2)$ ein solcher Blockplan zugeordnet werden kann und umgekehrt. 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- $2{\text{-}}(4n-1,2n-1,n-1)$ -Blockplan ${\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},\in )$ lässt sich zu einem $3{\text{-}}(4n,2n,n-1)$ -Blockplan ${\mathcal {E}}$ erweitern. Die Erweiterung sieht so aus: Man vereinbart ${\mathfrak {p}}'={\mathfrak {p}}\cup \{\infty \}$ mit einem zusätzlichen Punkt $\infty \not \in {\mathfrak {p}}$ als neue Punktmenge und ${\mathfrak {B}}'=\{X\cup \{\infty \}|X\in {\mathfrak {B}}\}\cup \{{\mathfrak {p}}\setminus X|X\in {\mathfrak {B}}\}$ als neue Blockmenge für ${\mathcal {E}}$ .^[1] Dann ist ${\mathcal {E}}=({\mathfrak {p}}',{\mathfrak {B}}',\in )$ der 3-Blockplan. Diese Erweiterung ist bis auf Isomorphie die einzig mögliche Erweiterung für den Hadamard-2-Blockplan ${\mathcal {I}}$ , so dass ${\mathcal {I}}={\mathcal {E}}_{x}$ für einen Punkt x in der Punktmenge von ${\mathcal {E}}$ gilt und ${\mathcal {E}}$ ein 3-Blockplan ist. ${\mathcal {E}}_{x}$ ist die Ableitung von ${\mathcal {E}}$ am Punkt x. Jeder $3{\text{-}}(4n,2n,n-1)$ -Blockplan ${\mathcal {E}}$ hat für $n\geq 2$ als Ableitung an jedem Punkt einen Hadamard-2-Blockplan. Ein 3-Blockplan ist genau dann stark auflösbar, wenn er ein Hadamard-3-Blockplan ist.

Übersicht über die kleinsten symmetrischen Blockpläne

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

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

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

Für Biplanes (symmetrische Blockpläne mit λ=2) können λ-chains 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 $a_{1}\cdot l_{1},a_{2}\cdot l_{2},\dotsc$ mit den Anzahlen $a_{1},a_{2},\dotsc$ und den Zyklenlängen $l_{1},l_{2},\dotsc$ 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

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 A,B,C . Sei die Anzahl aller Punkte, welche mit mehr als einem der insgesamt 4 Blöcke inzidiert. Sei die Häufigkeit des kleinsten , wenn A,B,C alle ${\tbinom {v-1}{3}}$ möglichen Kombinationen durchlaufen. Durchläuft nun auch der Indexblock sämtliche Möglichkeiten, so wird die Signatur in der Form $a_{1}\cdot q_{1},a_{2}\cdot q_{2},\dotsc$ mit den Anzahlen $a_{1},a_{2},\dotsc$ und den ermittelten $q_{1},q_{2},\dotsc$ 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 $a_{1}\cdot q_{{1a}}/q_{{1b}},\dotsc$ dargestellt.

Beispiel: In diesem (16,6,2)-Blockplan sind ein Indexblock sowie drei Blöcke A,B,C

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 A,B,C

alle ${\tbinom {15}{3}}$ 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

Thomas Beth, Dieter Jungnickel, Hanfried Lenz: Design Theory. 2. Auflage. B.I. Wissenschaftsverlag, London / New York / New Rochelle / Melbourne / Sidney 1999, ISBN 0-521-33334-2

Anmerkungen

↑ Die Blöcke von ${\mathcal {I}}$ können als Mengen von Punkten aufgefasst werden, da Hadamard-Blockpläne einfach sind.

Basierend auf einem Artikel in:

Wikipedia.de