Inzidenzstruktur bezeichnet in der Geometrie eine abstrakte Struktur, bestehend aus zwei Mengen von Objekten und einer Relation zur Beschreibung der Inzidenz. Die Menge des ersten Typs wird Punkte genannt und die zweite Menge Blöcke. Die Inzidenzrelation gibt aus der Menge aller möglichen Paare von Punkten und Blöcken nur jene an, die eine Inzidenz eines Punktes mit einem Block (z. B. einer Linie) bezeichnen. Durch die allgemein gehaltene Formulierung lassen sich zahlreiche Strukturen als Spezialfälle einer Inzidenzstruktur beschreiben.
mini|Veranschaulichung von Inzidenzstrukturen: Beispiele 1: Die Geraden sind verschiedene Blöcke – die Inzidenz lautet „Punkt liegt auf der Gerade“. Beispiel 2: Wie Beispiel 1, mit Kreisen anstelle der Geraden. Beispiel 3: Inzidenzmatrix: Zeilen und Spalten bezeichnen Punkte und Blöcke, der Zahlenwert beschreibt eine Inzidenz. Ausführliche Beschreibung der Beispiele im Text nebenan.
Definition Eine InzidenzstrukturBeutelspacher (1982), Abschnitt 1.2 Inzidenzstrukturen ist ein Tripel bestehend aus einer Menge , welche Punkte genannt wird, einer Menge , welche Blöcke genannt wird, einer Menge , der Relation, deren Elemente Inzidenzen oder Fahnen heißen. Weiter soll gelten In der Geometrie wird die Inzidenzrelation oft symmetrisch eingeführt; nach der Definition hier ist sie antisymmetrisch. Die symmetrische Inzidenz gewinnt man aus der antisymmetrischen I durch und umgekehrt: .
Für schreibt man und sagt, dass der Punkt mit dem Block inzidiert.
Die Relation heißt in diesem Zusammenhang Inzidenzrelation.
Beispiele 1) sei die Menge der Punkte in der euklidischen Ebene und die Menge der Geraden. Die Inzidenzrelation gibt an, ob ein Punkt mit einer Geraden inzidiert, was hier bedeutet: „ liegt auf “. Das Symbol bedeutet die Menge aller möglichen Punkt-Block-Paare . Da nicht jeder Punkt auf jeder Geraden liegt, ist die Menge der inzidenten Punkt-Gerade-Paare eine Teilmenge der möglichen Paare, bzw. . In diesem Fall ist die Inzidenzstruktur die reelle affine Ebene. 2) sei wieder die Menge der Punkte in der euklidischen Ebene, aber ist jetzt die Menge der Kreise. Die Inzidenz bedeutet hier wieder „Punkt liegt auf Block“. In Beispiel 1 und 2 sind die zugrunde liegenden Mengen der Punkte, Blöcke und Inzidenzen unendlich. Dabei ist im ersten Beispiel ein Block durch zwei Punkte eindeutig bestimmt, im zweiten durch drei (nicht kollineare) Punkte. Dadurch ergeben sich unterschiedliche Eigenschaften der Inzidenzstrukturen. 3) sei die Menge der Eckpunkte eines Quadrates und die Menge der Geraden durch je zwei dieser Punkte. Dann ist eine 12-elementige Teilmenge von . Bei endlichen Beispielen kann man die Inzidenz durch eine Matrix beschreiben, in der eine 1 bedeutet, dass eine Inzidenz zwischen den jeweiligen Elementen der Zeile und Spalte besteht, und 0, wenn keine Inzidenz besteht. In diesem Fall ist die Inzidenzstruktur das Minimalmodell einer affinen Ebene. In den Beispielen 1, 2 und 3 kann ein Block verstanden werden als die Menge der mit ihm inzidierenden Punkte. Die Inzidenzrelation ist dann die Enthaltenseinsrelation . Im folgenden Beispiel ist dies nicht möglich, da ein Punkt der Inzidenzstruktur ein Unterraum ist. In diesem Fall kann man aber die Inzidenzrelation als Teilmengenrelation auffassen. 4) sei die Menge der Ursprungsgeraden im euklidischen Raum, die Menge der Ursprungsebenen. Ein Punkt inzidiere mit einem Block , falls in enthalten ist. Die Inzidenzstruktur ist in diesem Fall eine projektive Ebene. 5) sei die Menge der Punkte der Einheitskugel im 3-dimensionalen euklidischen Raum, die Menge der Kreise auf der Einheitskugel und die Inzidenzrelation. Die Inzidenzstruktur ist in diesem Fall die reelle Möbius-Ebene.
Für wichtige Klassen von Inzidenzstrukturen gilt ein Dualitätsprinzip. Die endlichen Inzidenzstrukturen sind Studienobjekte in der endlichen Geometrie und damit auch in der Kombinatorik. Ihnen kann man eine endliche Menge von Parametern zuordnen, die z. B. angeben, mit wie vielen Blöcken zwei verschiedene Punkte im Durchschnitt inzidieren; eine endliche Inzidenzstruktur, bei der ein solcher Parameter nicht nur den Durchschnittswert, sondern in jedem Fall die tatsächliche Anzahl der Inzidenzen angibt, erfüllt eine Regularitätsbedingung. Nichtausgeartete Inzidenzstrukturen, die solche Regularitätsbedingungen erfüllen, können durch diese typisiert werden.
Grundlegende Begriffe und Definitionen für Inzidenzstrukturen Isomorphismen von Inzidenzstrukturen Seien und Inzidenzstrukturen. Eine bijektive Abbildung heißt Isomorphismus von auf , wenn gilt: bildet Punkte auf Punkte und Blöcke auf Blöcke ab und für alle Punkte und Blöcke von gilt:
Einfache Inzidenzstruktur Die Inzidenzstruktur heißt einfach, wenn für beliebige Blöcke gilt:
wenn also alle Blöcke durch die mit ihnen inzidierenden Punkte vollständig bestimmt sind. Gleichwertig dazu ist: ist einfach genau dann, wenn isomorph zu einer Inzidenzstruktur ist, wobei eine Teilmenge der Potenzmenge von ist.
Dualität Zu einer Inzidenzstruktur wird die duale Inzidenzstruktur so gebildet:
Die duale Inzidenzstruktur entsteht also aus , indem man die Blöcke die Rolle der Punkte spielen lässt und umgekehrt. Natürlich gilt
Vertauscht man in einer Aussage A über Inzidenzstrukturen die Wörter „Punkt“ und „Block“, so erhält man die zu A duale Aussage.
Für eine Klasse von Inzidenzstrukturen wird mit die Klasse der dualen Inzidenzstrukturen bezeichnet.
Eine konkrete Inzidenzstruktur heißt zu sich selbst dual, wenn es einen Isomorphismus gibt. Mit anderen Worten: ist genau dann zu sich selbst dual, wenn das Dualitätsprinzip für die Klasse der zu isomorphen Strukturen gilt.
Notation und grundlegende Begriffe Eine Inzidenzstruktur heißt endlich, wenn ihre Punktmenge und ihre Blockmenge endlich sind. Eine Inzidenzstruktur heißt ausgeartet, wenn sie einen Block enthält, für den es keine zwei Punkte gibt, die nicht mit diesem Block inzidieren, sonst heißt die Struktur nichtausgeartet. Eine Inzidenzstruktur ist also genau dann nichtausgeartet, wenn für jeden Block mindestens zwei verschiedene Punkte existieren, die nicht mit B inzidieren. Ist eine Teilmenge der Punktmenge einer Inzidenzstruktur, dann wird die Menge aller Blöcke, die mit jedem Punkt dieser Teilmenge inzidiert, als notiert; ist die Inzidenzstruktur endlich, dann wird die Anzahl dieser Blöcke als notiert. Die Symbole und sind entsprechend dual als Punktmengen bzw. deren Anzahl für Mengen von Blöcken einer (endlichen) Inzidenzstruktur erklärt. Formal:
Aus der Definition ergibt sich, dass die Menge aller Blöcke bedeutet, wenn die leere Menge als Teilmenge der Punktmenge angesehen wird, und die Menge aller Punkte, wenn sie als Teilmenge der Blockmenge angesehen wird.
Parameter einer endlichen Inzidenzstruktur, Punkt- und Blockgrad Einer endlichen Inzidenzstruktur werden für und die folgenden Parameter zugeordnet:
Der Parameter gibt also an, wie viele Blöcke im Durchschnitt mit verschiedenen Punkten inzidieren und der Parameter wie viele Punkte im Durchschnitt auf verschiedenen Blöcken zugleich liegen. Der Parameter ist die Gesamtzahl der Punkte und die Gesamtzahl der Blöcke der endlichen Inzidenzstruktur.
Darüber hinaus wird, vor allem im Zusammenhang mit linearen Räumen, der Begriff Grad definiert: Der Grad eines Punktes ist die Anzahl der Blöcke, mit denen inzidiert. Der Grad eines Blockes bzw. einer Geraden ist die Anzahl der Punkte, mit denen inzidiert.
Damit ist der Durchschnitt aller Grade von Punkten und der Durchschnitt aller Grade von Blöcken.
Regularitätsbedingungen und Typen von endlichen Inzidenzstrukturen Für eine endliche Inzidenzstruktur werden die folgenden RegularitätsbedingungenDembowski (1961) definiert, anhand derer diese Strukturen klassifiziert werden können: Je verschiedene Punkte inzidieren mit genau Blöcken. Mit anderen Worten: Für alle -elementigen Teilmengen gilt Je verschiedene Blöcke inzidieren mit genau Punkten. Mit anderen Worten: Für alle -elementigen Teilmengen gilt
Eine endliche Inzidenzstruktur, die die Regularitätsbedingungen und erfüllt, aber weder die Bedingung noch die Bedingung wird als Inzidenzstruktur vom Typ bezeichnet. Eine endliche Inzidenzstruktur, die (mindestens) die Regularitätsbedingungen erfüllt, wird als taktische Konfiguration (nach MooreMoore (1896)) bezeichnet. Typische Beispiele sind die verallgemeinerten Vierecke. Eine endliche Inzidenzstruktur, die mit dem Parameter erfüllt, heißt Inzidenzgeometrie.
Inzidenzmatrix → Der hier beschriebene Begriff Inzidenzmatrix für eine endliche Inzidenzstruktur kann als Verallgemeinerung des Begriffes Inzidenzmatrix eines ungerichteten Graphen angesehen werden.
Eine endliche Inzidenzstruktur mit Punkten und Blöcken kann auch durch eine -Matrix repräsentiert werden. Dazu nummeriert man die Punkte von bis und die Blöcke von bis durch und trägt in die Matrix die Beziehungen der Punkte zu den Blöcken ein:
Die Matrix heißt dann eine Inzidenzmatrix der endlichen Inzidenzstruktur.Beutelspacher (1982), S. 41.
Natürlich liefern verschiedene Nummerierungen der Punkt- und Blockmenge im Allgemeinen verschiedene Inzidenzmatrizen. Offenbar ist jede Matrix, deren Elemente nur und sind, Inzidenzmatrix einer geeigneten endlichen Inzidenzstruktur und diese ist durch die Inzidenzmatrix vollständig bestimmt.
Es werden, vor allem im Zusammenhang mit Hadamard-Matrizen auch -Inzidenzmatrizen verwendet, bei denen die Einträge in der oben beschriebenen Matrix durch ersetzt werden.Beth, Jungnickel, Lenz, I §9: Hadamard designs
Ableitung einer Inzidenzstruktur Für eine endliche oder unendliche Inzidenzstruktur bezeichnet man für einen Punkt die nachfolgende definierte Struktur als Ableitung von nach oder auch am Punkt abgeleitete Inzidenzstrukturenglisch: derived structure at a point (Beth, Jungnickel, Lenz, Definition I.9.8)Beutelspacher (1982), 4. Nichtexistenzsätze
Die Ableitung nach besteht also aus allen Punkten außer als Punktmenge den Blöcken durch als Blockmenge mit der induzierten Inzidenz, In diesem Fall bezeichnet man als Erweiterung von Eine Erweiterung ist im Allgemeinen (wie auch die „Aufleitung“ als Umkehrung der „Ableitung“ in anderen Teilgebieten der Mathematik) ohne zusätzliche Bedingungen durch die ursprüngliche Struktur nicht eindeutig bestimmt.
Der Begriff wird zum Beispiel benutzt, wenn aus der Nichtexistenz von Blockplänen mit bestimmten Parametern auf die gewisser größerer Blockpläne geschlossen wird.
Wie sich die Ableitung auf die Parameter spezieller Inzidenzstrukturen auswirken kann, ist beispielhaft im Artikel Wittscher Blockplan, dort insbesondere im Abschnitt Inzidenzparameter der Wittschen Blockpläne dargestellt.
Beispiel Ist die Inzidenzstruktur eine Möbius-Ebene, so ist die Ableitung in jedem Punkt eine affine Ebene und damit eine einfachere Struktur (s. Möbius-Ebene).
Eigenschaften Dualitätsprinzip Ist eine Aussage, die für alle Inzidenzstrukturen einer Klasse gilt, so gilt die duale Aussage für alle Inzidenzstrukturen aus Ist für eine Klasse von Inzidenzstrukturen , so sagt man „für gilt das Dualitätsprinzip“. Dann ist für jede Aussage die für alle Inzidenzstrukturen aus zutrifft, auch für alle diese Inzidenzstrukturen richtig.
Beispiele Das Dualitätsprinzip gilt für die Klasse der endlichen Inzidenzstrukturen, der Inzidenzstrukturen, in denen jeder Punkt mit einer konstanten Anzahl von Blöcken und jeder Block mit einer konstanten Anzahl von Punkten inzidiert, der projektiven Ebenen, der projektiven Ebenen der Lenz-Klasse VII (das sind genau die desarguesschen projektiven Ebenen), der endlichen Inzidenzstrukturen, deren Inzidenzmatrix als symmetrische Matrix gewählt werden kann.