Symmetrischer Blockplan

Ein Blockplan (auch Block-Design oder kombinatorisches Design) ist eine endliche Inzidenzstruktur, die insbesondere in der endlichen Geometrie, der Kombinatorik sowie der statistischen Versuchsplanung von Bedeutung ist. Blockpläne sind eine gemeinsame Verallgemeinerung der endlichen affinen Ebenen und der endlichen projektiven Ebenen.

Wichtige Methoden zur Charakterisierung von Blockplänen und zur Konstruktion neuer Blockpläne aus bekannten sind die Auflösung und die taktische Zerlegung eines Blockplanes. Die Auflösung verallgemeinert das Konzept des Parallelismus eines Blockplanes, wie es dieser Artikel beschreibt, und ist selbst ein Spezialfall der taktischen Zerlegung.

Definitionen und Schreibweisen

Sei ${\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)$ eine endliche Inzidenzstruktur, bei der die Elemente von ${\mathfrak {p}}$ als Punkte und die Elemente von ${\mathfrak {B}}$ als Blöcke bezeichnet werden. Des Weiteren seien $t,v,k,\lambda \in \mathbb {N}$ natürliche Zahlen, dann wird die Inzidenzstruktur ${\mathcal {I}}$ als $t-(v,k,\lambda )$ Blockplan bezeichnet, wenn die folgenden Axiome gelten:

• (B1) ${\mathcal {I}}$ hat genau $v$ Punkte ($|{\mathfrak {p}}|=v_{0}=v$),
• (B2) jeder Block von ${\mathcal {I}}$ inzidiert mit genau $k$ Punkten ($v_{1}=k$),
• (B3) für jede Punktmenge $T\subseteq {\mathfrak {p}}$ mit $t$ verschiedenen Punkten existieren genau $\lambda$ verschiedene Blöcke, die jeweils mit allen Punkten von $T$ inzidieren ($b_{t}=\lambda$) und
• (B4) $2\leq k\leq v-2$, d.h. ${\mathcal {I}}$ ist eine nichtausgeartete Inzidenzstruktur.

Als alternative Bezeichnung für einen $t-(v,k,\lambda )$ Blockplan wird auch $S_{\lambda }(t,k;v)$ verwendet. Im Falle von $\lambda =1$ schreibt man auch einfach $S(t,k;v)$ und spricht von einem Steinersystem (nach Jakob Steiner). Ein $2-(v,3,1)$ Blockplan ($S(2,3;v)$) wird auch als Steiner-Tripel-System bezeichnet. Teilweise wird ein Blockdesign auch als ${\mathcal {I}}(v,b,r,k,\lambda )$ geschrieben, der zusätzliche Parameter r wird weiter unten erläutert.

Einen $t-(v,k,\lambda )$ Blockplan bezeichnet man oft kurz auch t-Blockplan und einen $2-(v,k,\lambda )$ Blockplan einfach als Blockplan, da $t=2$ der am meisten verwendete Fall ist.

Die konstante Anzahl aller Blöcke $B\in {\mathfrak {B}}$ von ${\mathcal {I}}$ durch einen Punkt $p\in {\mathfrak {p}}$ von ${\mathcal {I}}$ wird mit $r$ bezeichnet und die Anzahl aller Blöcke von ${\mathcal {I}}$ mit $b_{0}=b=|{\mathcal {B}}|$. Ein Blockplan, der genauso viele Blöcke wie Punkte besitzt ($v=b$), wird als symmetrisch oder projektiv bezeichnet.

In Anlehnung an bestimmte geometrische Modelle für einen Blockplan werden seine Blöcke gelegentlich auch als Geraden, Kreise, Ebenen oder Ähnliches bezeichnet. Wenn ein Punkt p mit einem Block B inzidiert ($(p,B)\in I$), so sind auch die folgen Sprechweisen üblich: p liegt auf B oder B geht durch p. Inzidiert ein Punkt mit mehreren Blöcken, so sagt man auch, dass die Blöcke sich in p schneiden.

Blockpläne, bei denen ein Block mit allen Punkten inzidiert, oder bei denen die k-elementigen Teilmengen der Punktmenge genau den Blöcken entsprechen, werden als triviale Blockpläne bezeichnet.

Ein Block B muss formal von der mit ihm inzidierenden Punktmenge (B) unterschieden werden, allerdings ist es in der Praxis meist möglich, einen Block mit seiner inzidierenden Punktmenge zu identifizieren und die Inzidenzrelation als mengentheoretisches Enthaltensein zu interpretieren. Solche Blockpläne werden auch als einfach bezeichnet (vgl. die Beispiele im Artikel „Inzidenzstruktur“).

Eigenschaften

• Für die Anzahl der Blöcke eines $t-(v,k,\lambda )$ Blockplans gilt: $b=\lambda \cdot {v \choose t}\cdot {k \choose t}^{-1}.$
• Mit $b_{i}$ für $i=1,\ldots ,t$ bezeichnet man die Anzahl der Blöcke die mit allen Punkten einer beliebigen Punktmenge M mit i Punkten inzidieren ($M\subset {\mathfrak {p}},\,|M|=i$), für diese gilt: $b_{i}=\lambda \cdot {v-i \choose t-i}\cdot {k-i \choose t-i}^{-1}.$
• Für $2-(v,k,\lambda )$ Blockpläne ergibt sich aus den beiden Formeln unter Berücksichtigung von $b_{1}=r$:

$b\cdot k=v\cdot r\quad {\text{und}}\quad \lambda \cdot (v-1)=r\cdot (k-1)$

• Außerdem gilt für die $2-(v,k,\lambda )$ Blockpläne die Fisher-Ungleichung: $b\geq v\quad {\text{und}}\quad r\geq k$.

Neben den unten bei den Beispielen erwähnten, endlichen, projektiven und affinen Räumen stehen Blockpläne in Wechselbeziehungen zu vielen anderen Strukturen der Kombinatorik. So ist zum Beispiel die Existenz eines $2-(4n-1,2n-1,n-1)$ Blockplans ($n\in \mathbb {N} ,n\geq 2$) äquivalent zur Existenz einer Hadamard-Matrix der Ordnung $4n$. Aus diesem Grund werden solche Blockpläne auch als Hadamard Blockpläne bezeichnet. Den Zusammenhang zwischen Codes und Blockplänen beschreibt der Satz von Assmus-Mattson.

Eine zentrale Frage in der Theorie der Blockpläne ist, für welche Werte der Parameter $t,v,k,\lambda$ überhaupt ein Blockplan existiert. Während eine allgemeine Antwort auf diese Frage noch aussteht, existiert nach einem Resultat von L. Teirlinck (1987) doch zu jedem $t\in \mathbb {N}$ ein nichttrivialer t-Blockplan. Außerdem gibt es eine Reihe von notwendigen Kriterien für die Existenz bestimmter Blockpläne, 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.

Symmetrische Blockpläne

Symmetrische Blockpläne können unter den 2-Blockplänen durch verschiedene, gleichwertige Aussagen charakterisiert werden: Sei ${\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)$ ein $2-(v,k,\lambda )$-Blockplan, sei $b=b_{0}$ die Gesamtzahl seiner Blöcke und sei A eine Inzidenzmatrix dieses Blockplanes. Dann sind die folgenden Aussagen gleichwertig:

1. Die Anzahl der Punkte ist gleich der Anzahl der Blöcke $(v=b)$ und damit gilt auch $r=k$, das heißt ${\mathcal {I}}$ ist symmetrisch. Es gilt $\lambda \cdot (v-1)=k\cdot (k-1)$
2. Die Zahl der Blöcke, mit denen ein beliebiger Punkt inzidiert, ist gleich der Zahl der Punkte, mit denen ein beliebiger Block inzidiert $(v_{1}=b_{1})$.
3. $A\cdot A^{T}=(k-\lambda )\cdot E+\lambda \cdot J,$ hierbei ist E die $v\times v$-Einheitsmatrix, J die $v\times v$-Einsmatrix
4. $A^{T}\cdot A=(k-\lambda )\cdot E+\lambda \cdot J,$ hierbei ist E die $b\times b$-Einheitsmatrix, J die $b\times b$-Einsmatrix
5. Je zwei verschiedene Blöcke schneiden sich in genau $\lambda$ Punkten.
6. Je zwei verschiedene Blöcke haben eine konstante, positive Anzahl von Punkten gemeinsam, das heißt, ${\mathcal {I}}$ erfüllt die Regularitätsbedingung $(P_{2})$. Siehe Inzidenzstruktur#Regularitätsbedingungen und Typen von endlichen Inzidenzstrukturen.
7. ${\mathcal {I}}$ hat als Inzidenzstruktur den Typ (2,2), das heißt, ${\mathcal {I}}$ erfüllt die Regularitätsbedingungen $(P_{1}),(P_{2}),(B_{1}),(B_{2})$.

Als Ordnung eines symmetrischen $2-(v,k,\lambda )$ Blockplans bezeichnet man die Differenz $k-\lambda$.

Projektive Ebene

Ein symmetrischer $2-(n^{2}+n+1,n+1,1)$ - Blockplan wird als Projektive Ebene der Ordnung $n$ bezeichnet.

Biplane

Ein symmetrischer $2-({\frac {n^{2}+3n+4}{2}},n+2,2)$ - Blockplan wird als Biplane der Ordnung $n$ bezeichnet. Es sind bislang nur Biplanes der Ordnungen 3, 4, 7, 9 und 11 bekannt .

Triplane

Ein symmetrischer $2-({\frac {n^{2}+5n+9}{3}},n+3,3)$ - Blockplan wird als Triplane der Ordnung $n$ bezeichnet. Es sind bislang nur Biplanes der Ordnungen 4, 6, 7, 9 und 12 bekannt .

Hadamard-Blockplan

Ein symmetrischer $2-(4\lambda +3,2\lambda +1,\lambda )$ - Blockplan wird als Hadamard-Blockplan (genauer: Hadamard-2-Blockplan) bezeichnet. Der Name rührt 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 nur Einträge 1 enthalten, da H normalisiert ist, gestrichen und die verbleibende Matrix wird als (1,-1)-Inzidenzmatrix des Hadamard-Blockplanes verwendet. Daher gilt:

Ein symmetrischer $2-(4n-1,2n-1,n-1)$ - Blockplan $(n\geq 2)$ existiert genau dann, wenn eine $4n\times 4n$-Hadamard-Matrix existiert.

Erweiterter Hadamard-Blockplan

Jeder Hadamard-$2-(4n-1,2n-1,n-1)$-Blockplan ${\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},\in )$ lässt sich zu einem $3-(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}}$. 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-(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.

Oval

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.

Übersicht über die kleinsten symmetrischen Blockpläne

In der nachfolgenden Tabelle sind die Blockpläne nach λ und nach n - λ aufgelistet. Die Einschränkung n - λ >= 1 ist äquivalent zu k <= v / 2.

Die dazu komplementären Blockpläne (k > v / 2) sind hier nicht aufgeführt. Sie entstehen durch Vertauschung der Nullen mit den Einsen 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.

	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)

Parallelismen und affine Blockpläne

Ein Parallelismus eines Blockplans ${\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)$ ist eine Äquivalenzrelation auf der Menge der Blöcke, für die das euklidische Parallelenpostulat gilt:

• Zu jedem Block $B\in {\mathfrak {B}}$ und jedem Punkt $p\in {\mathfrak {p}}$ gibt es genau einen Block $C$ inzident mit $p$ der zu $B$ parallel ist.

Hierbei werden Blöcke als parallel (Schreibweise $B\parallel C$) bezeichnet, wenn sie in derselben Äquivalenzklasse liegen. Die Äquivalenzklassen selbst werden auch als Parallelenklassen oder Parallelenscharen bezeichnet. Für zwei parallele Blöcke $B,C\in {\mathfrak {B}}$ gilt, dass sie (genauer: die mit ihnen inzidierenden Punktmengen) entweder identisch oder disjunkt sind:

$B\parallel C\Rightarrow (B)=(C){\text{ oder }}(B)\cap (C)=\emptyset$

Ein Parallelismus eines Blockplans, bei dem zwei beliebige, nicht parallele Blöcke stets dieselbe Anzahl von Punkten gemeinsam haben, heißt affin und der zugehörige Blockplan wird als affiner Blockplan bezeichnet. Während im Allgemeinen ein Blockplan mehrere Parallelismen zulassen kann, ist in einem affinen Blockplan der Parallelismus eindeutig bestimmt und es gilt auch die Umkehrung der obigen Beziehung:

$B\parallel C\Leftrightarrow (B)=(C){\text{ oder }}(B)\cap (C)=\emptyset$

Für Blockpläne mit Parallelismen gilt der Satz von Bose, der für diesen Fall eine Verschärfung der Fisher-Ungleichung darstellt.

Beispiele

Die Wittschen Blockpläne (im engeren Sinn) sind einfache 5-Blockpläne, ihre Ableitungen, die oft auch als Wittsche Blockpläne bezeichnet werden, liefern Beispiele für nichttriviale einfache 4- und 3-Blockpläne.

Affine Geometrien als Blockpläne

Der affine Raum der Dimension $n\geq 2$ über dem endlichen Körper mit q Elementen $\mathbb {F} _{q}$ wird als $AG(n,q)$ notiert. Er wird zu einem Blockplan $AG_{d}(n,q)$, indem man die Punktmenge des affinen Raumes als Menge der Punkte und die d-dimensionalen affinen Teilräume $(1\leq d<n)$ als Blöcke verwendet. Genauer handelt es sich bei $AG_{d}(n,q)$ um einen $2-(v,k,\lambda )$-Blockplan. Der gewöhnliche Parallelismus der affinen Geometrie ist ein Parallelismus für den Blockplan und der Blockplan wird damit genau dann zu einem affinen Blockplan, wenn $d=n-1$ gilt, also die Blöcke Hyperebenen des Raumes sind. Die Parameter des Blockplanes $AG_{d}(n,q)$ lauten:

$v=q^{n},k=q^{d},\lambda ={\begin{bmatrix}n-1\\d-1\end{bmatrix}}_{q}.$

Hier steht ${\begin{bmatrix}n\\i\end{bmatrix}}_{q}$ für den Gaussschen Binomialkoeffizienten, der durch die Formel ${\begin{bmatrix}n\\i\end{bmatrix}}_{q}={\frac {(q^{n}-1)(q^{n-1}-1)\cdots (q^{n-i+1}-1)}{(q^{i}-1)(q^{i-1}-1)\cdots (q-1)}}$ (für $0<i\leq n)$ berechnet werden kann.

Die Räume $AG_{2}(n,2),(n\geq 3)$ sind sogar 3-Blockpläne mit $\lambda =1$. Speziell ist $AG_{2}(3,2)$ mit seinem geometrischen Parallelismus ein affiner $3-(8,4,1)$-Blockplan.

Projektive Geometrien als Blockpläne

Der projektive Raum der Dimension $n\geq 2$ über dem endlichen Körper $\mathbb {F} _{q}$ wird als $PG(n,q)$ notiert. Der Blockplan $PG_{d}(n,q)$ hat als Punktmenge die Menge der projektiven Punkte und als Blockmenge die Menge der d-dimensionalen projektiven Teilräume $(1\leq d<n)$ des $PG(n,q)$. Dies ist ein $2-(v,k,\lambda )$-Blockplan mit den Parametern

$v={\begin{bmatrix}n+1\\1\end{bmatrix}}_{q}={\frac {q^{n+1}-1}{q-1}},k={\begin{bmatrix}d+1\\1\end{bmatrix}}_{q}={\frac {q^{d+1}-1}{q-1}},\lambda ={\begin{bmatrix}n-1\\d-1\end{bmatrix}}_{q}.$

Im Falle $d=n-1$ also falls die Blöcke die Hyperebenen des Raumes sind, ist der Blockplan symmetrisch.

Anschauliche Beispiele

Als Spezialfälle der obengenannten klassischen geometrischen Räume kann man eine endliche projektive Ebene der Ordnung $q$ als einen $2-(q^{2}+q+1,q+1,1)$ Blockplan und eine endliche affine Ebene der Ordnung $q$ als einen $2-(q^{2},q,1)$ Blockplan auffassen. Hierbei entsprechen die Punkte der Ebene den Punkten des Blockplans und die Geraden der Ebene den Blöcken des Blockplans. Allerdings wird die Existenz der entsprechenden Ebene der Ordnung q vorausgesetzt und diese ist nicht für alle $q\in \mathbb {N}$ gegeben.

Kleine Ebenen, siehe auch die Abbildungen am Ende des Abschnitts:

• Die projektive Ebene der Ordnung 2, $PG_{1}(2,2)$ (die Fano-Ebene) ist ein symmetrischer $2-(7,3,1)$ Blockplan zugleich ist sie „der“ kleinste Hadamard-Blockplan.
• Die affinen Ebenen der Ordnung 2 und 3 $AG_{1}(2,2)$ und $AG_{1}(2,3)$ bilden mit ihrer gewöhnlichen und einzig möglichen Parallelität einen affinen $2-(4,2,1)$ Blockplan bzw. $2-(9,3,1)$ Blockplan.

$PG(2,2)$	$AG(2,2)$	$AG(2,3)$
7 Pkte, 7 Blöcke mit je 3 Pkten	4 Pkte, 6 Blöcke mit je 2 Pkten	9 Pkte, 12 Blöcke mit je 3 Pkten

Literatur

• Thomas Beth, Dieter Jungnickel, Hanfried Lenz: Design Theory. 2. Auflage. B.I. Wissenschaftsverlag, London/New York/New Rochelle/Melbourne/Sidney 1999 (Erstauflage 1986), ISBN 0-521-33334-2. 
• Albrecht Beutelspacher: Einführung in die endliche Geometrie. I. Blockpläne. B.I. Wissenschaftsverlag, Mannheim/Wien/Zürich 1982, ISBN 3-411-01632-9. 
• Jacobus Hendricus Van Lint, Richard Michael Wilson: A Course in Combinatorics. Cambridge University Press, 1992, ISBN 0-521-42260-4. 

Weblinks

• Eric W. Weisstein: block design. In: MathWorld (englisch).
• Skript Algebraische Strukturen und Diskrete Mathematik,S. 67 (PDF-Datei; 1,01 MB)
• block design in der Encyclopaedia of Mathematics