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.Beutelspacher, S. 43 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.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
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: , 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
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.Beth, Jungnickel, Lenz: 2.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 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.Beth, Jungnickel, Lenz (1986, 1999), Appendex-Table B
Triplane 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.Sanja Rukavina: Some new triplanes of order twelve. Glas. Mat. Vol 36 (2001) 105-125
Hadamard-Blockplan Jeder symmetrische -Blockplan wird als Hadamard-Blockplan (genauer: Hadamard-2-Blockplan) bezeichnet.Beth, Jungnickel, Lenz (1986, 1999), I.9 Hadamard designs Der Name kommt daher, dass jeder normalisierten - Hadamard-Matrix ein solcher Blockplan zugeordnet werden kann und umgekehrt.Beth, Jungnickel, Lenz (1986, 1999), Lemma I.9.3 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.Beth, Jungnickel, Lenz (1986, 1999), Theorem I.9.9 Die Erweiterung sieht so aus: Man vereinbart mit einem zusätzlichen Punkt als neue Punktmenge und als neue Blockmenge für .Die Blöcke von können als Mengen von Punkten aufgefasst werden, da Hadamard-Blockpläne einfach sind. 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.Beth, Jungnickel, Lenz (1986, 1999), Theorem II.8.10, Corollary II.8.11 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 - λ12345678910111213141516λ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)(22,7,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