Steinersches Tripel-System

Ein Blockplan ist eine Inzidenzstruktur, die insbesondere in der endlichen Geometrie, der Kombinatorik, sowie der statistischen Versuchsplanung von Bedeutung ist.

Definition

Sei D = (P,B,I) eine Inzidenzstruktur bei der die Elemente von P als Punkte und die Elemente von B als Blöcke bezeichnet werden. Des Weiteren seien $t,v,k,\lambda \in \mathbb{N}$, dann wird die Inzidenzstruktur als t − (v,k,λ) Blockplan bezeichnet, wenn die folgenden Axiome gelten:

• (B1) D hat genau v Punkte ( | P | = v)
• (B2) jeder Block von D inzidiert mit genau k Punkten
• (B3) für jede Punktmenge T mit t Punkten existieren genau λ Blöcke, die jeweils mit allen Punkten von T inzidieren.
• (B4) $2 \leq k \leq v-2$

Als alternative Bezeichnung für einen t − (v,k,λ) Blockplan wird auch S_λ(t,v,k) verwendet. Im Falle von λ = 1 schreibt man auch einfach S(t,v,k) und spricht von einem Steiner-System (nach Jakob Steiner). Ein 2 − (v,3,1) Blockplan (S(2,v,3)) wird auch als Steiner-Tripel-System bezeichnet.

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

Die konstante Anzahl aller Blöcke von D durch einen Punkt von D wird mit r bezeichnet und die Anzahl aller Blöcke von D selbst ( | D | ) mit b. Ein Blockplan, der genauso viele Blöcke wie Punkte besitzt, (v = b) wird als symmetrisch oder projektiv bezeichnet.

In Anlehnung an geometrischen Hintergrund für einen bestimmten Blockplan werden seine Blöcke gelegentlich auch als Geraden, Kreise oder Ebenen bezeichnet. Wenn ein Punkt p mit einem Block b inzidiert ($p\, I\, b$), 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 ($k \leq t$) genau den Blöcken entsprechen werden als triviale Blockpläne bezeichnet.

Ein Block b ist formal von der mit ihm inzidierenden Punktmenge (b) zu unterscheiden, 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.

Beispiele und Eigenschaften

Man kann Blockpläne aus endlichen affinen Räumen und endlichen projektiven Räumen konstruieren, insbesondere kann man eine endliche projektive Ebene der Ordnung n als einen 2 − (n² + n + 1,n + 1,1) Blockplan und eine endliche affine Ebene der Ordnung n als einen 2 − (n²,n,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 n vorausgesetzt und diese ist nicht für alle $n\in \mathbb{N}$ gegeben. Einfache Beispiele sind die projektive Ebene der Ordnung 2 PG(2,2) (Fano-Ebene), die ein 2 − (7,3,1) Blockplan ist und die affinen Ebenen der Ordnung 2 und 3 AG(2,2) und AG(2,3), die einen 2 − (4,2,1) Blockplan bzw. einen 2 − (9,3,1) Blockplan bilden.

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

Für die Anzahl der Blöcke eines t − (v,k,λ) Blockplans gilt:

$b=\lambda\cdot\frac{{v \choose t}}{{k \choose t}}$

Mit b_i für $i=1,\ldots,t$ bezeichnet man die Anzahl der Blöcke die mit allen Punkten einer Punktmenge I der Größe i inzidieren ($I \subset P,\,|I|=i$), für diese gilt:

$b_i=\lambda\cdot\frac{{v-i \choose t-i}}{{k-i \choose t-i}}$

Für 2 − (v,k,λ) Blockpläne ergibt sich aus den beiden Formeln unter Berücksichtigung von b₁ = 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,λ) Blockpläne die Fisher-Ungleichung: $b\geq v \quad \text{und} \quad r\geq k$

Neben den oben erwähnten 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}$) ä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,λ überhaupt ein Blockplan existiert. Während eine umfassende Antwort auf diese Frage ein ungelöstes Problem ist, so existiert nach einem Resultat von L. Teirlinck (1987) jedoch zu jedem $t\in \mathbb{N}$ ein nichttrivialer t-Blockplan.^{[1] [2]}. Des Weiteren gibt es eine Reihe von notwendigen Kriterien für die Existenz bestimmter Blockpläne anhand deren man viele Parameterkombinationen ausschließen kann. Wichtige Beispiele hierfür sind die verallgemeinerte Fisher-Ungleichung (auch Satz von Ray-Chaudhuri-Wilson genannt) und der Satz von Bruck-Ryser-Chowla.

Parallelismen und affine Blockpläne

Ein Parallelismus eines Blockplans D = (P,B,I) ist eine Äquivalenzrelation auf der Menge der Blöcke für die das euklidische Parallelenpostulat gilt:

• Zu jedem Block $b \in B$ und jeden Punkt $p \in P$ gibt es genau einen Block $b^\prime$ inzident mit p der zu b parallel ist.

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

$a \parallel b \Rightarrow (a)=(b) \text{ oder } (a)\cap (b) = \emptyset$

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

$a \parallel b \Leftrightarrow (a)=(b) \text{ oder } (a)\cap (b) = \emptyset$

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

Einzelnachweise

1. ↑ L. Teirlinck: Nontrivial t-designs without repeated blocks exist for all t Discrete Math. 65,301-11
2. ↑ J.H. van Lint, R.M. Wilson: A Course in Combinatorics. S. 195, Cambridge University Press 1992,ISBN 0-521-42260-4

Literatur

• A. Beutelspacher: Einführung in die endliche Geometrie I. S. 40, Bibliographisches Institut 1983, ISBN 3-411-01648-5.
• J.H. van Lint, R.M. Wilson: A Course in Combinatorics. S. 188, Cambridge University Press 1992, ISBN 0-521-42260-4.

Weblinks

• Eric W. Weisstein: block design auf MathWorld (englisch)
• Skript Algebraische Strukturen und Diskrete Mathematik,S. 67