imported>PhiRho~dewiki: /* Definition */ Komma ergänzt

2025-12-05T16:32:20Z

Definition: Komma ergänzt

Neue Seite

'''Inzidenzstruktur''' bezeichnet in der [[Geometrie]] eine abstrakte [[Mathematische Struktur|Struktur]], bestehend aus zwei [[Menge (Mathematik)|Mengen]] von Objekten und einer [[Relation (Mathematik)|Relation]] zur Beschreibung der [[Inzidenz (Geometrie)|Inzidenz]]. Die Menge des ersten Typs wird ''[[Punkt (Geometrie)|Punkt]]e'' genannt und die zweite Menge ''Blöcke''. Die '''Inzidenzrelation''' gibt aus der Menge aller möglichen [[Geordnetes Paar|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.

[[Datei:Inzidenz-struktur.svg|mini|Veranschaulichung von Inzidenzstrukturen:<br />
Beispiele 1: Die [[Gerade]]n sind verschiedene Blöcke – die Inzidenz lautet „Punkt liegt auf der Gerade“.<br />
Beispiel 2: Wie Beispiel 1, mit [[Kreis]]en anstelle der Geraden.<br />
Beispiel 3: [[Inzidenzmatrix]]: Zeilen und Spalten bezeichnen Punkte und Blöcke, der Zahlenwert beschreibt eine Inzidenz.<br />
Ausführliche Beschreibung der Beispiele im Text nebenan.]]

== Definition ==
Eine ''Inzidenzstruktur''<ref name="BP12">Beutelspacher (1982), Abschnitt 1.2 Inzidenzstrukturen</ref> ist ein [[Tupel|Tripel]] <math>\mathcal{I} = (\mathfrak{p},\mathfrak{B},I)</math> bestehend aus
* einer Menge <math>\mathfrak{p}</math>, welche ''Punkte'' genannt wird,
* einer Menge <math>\mathfrak{B}</math>, welche ''Blöcke'' genannt wird,
* einer Menge <math>I\subseteq \mathfrak{p}\times\mathfrak{B}</math>, der Relation, deren Elemente ''Inzidenzen'' oder ''Fahnen'' heißen.
Weiter soll gelten
:<math>\mathfrak{p}\cap\mathfrak{B} = \emptyset{\;}.</math><ref>In der Geometrie wird die Inzidenzrelation oft ''symmetrisch'' eingeführt; nach der Definition hier ist sie ''antisymmetrisch''. Die symmetrische Inzidenz <math>I^\ast</math> gewinnt man aus der antisymmetrischen ''I'' durch <math>I^\ast = I\cup I^{-1}</math> und umgekehrt: <math>I = I^\ast\cap(\mathfrak{p}\times\mathfrak{B})</math>.</ref>

Für <math>(p,B)\in I</math> schreibt man <math>p\mathrel{\ I\ }B</math> und sagt, dass der Punkt <math>p</math> mit dem Block <math>B</math> inzidiert.

Die Relation <math>I</math> heißt in diesem Zusammenhang '''Inzidenzrelation'''.

== Beispiele ==
* 1) <math>\mathfrak{p}</math> sei die Menge der ''Punkte'' in der [[Euklidische Ebene|euklidischen]] [[Ebene (Mathematik)|Ebene]] und <math>\mathfrak{B}</math> die Menge der ''Geraden''. Die Inzidenzrelation <math>I</math> gibt an, ob ein Punkt <math>p</math> mit einer Geraden <math>G</math> inzidiert, was hier bedeutet: „<math>p</math> liegt auf <math>G</math>“. Das Symbol <math> \mathfrak{p}\times\mathfrak{B} </math> bedeutet die Menge aller ''möglichen'' Punkt-Block-Paare <math>(p,G)</math>. Da nicht jeder Punkt auf jeder Geraden liegt, ist die Menge der inzidenten Punkt-Gerade-Paare <math>I</math> eine [[Teilmenge]] der möglichen Paare, bzw. <math>I\subseteq \mathfrak{p}\times\mathfrak{B}</math>. In diesem Fall ist die Inzidenzstruktur die reelle [[affine Ebene]].
* 2) <math>\mathfrak{p}</math> sei wieder die Menge der Punkte in der euklidischen Ebene, aber <math>\mathfrak{B}</math> 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 [[kollinear]]e) Punkte. Dadurch ergeben sich unterschiedliche Eigenschaften der Inzidenzstrukturen.
* 3) <math>\mathfrak{p} = \{a,b,c,d\}</math> sei die Menge der Eckpunkte eines [[Quadrat]]es und <math>\mathfrak{B} = {A,B,C,D,E,F}</math> die Menge der Geraden durch je zwei dieser Punkte. Dann ist <math>I = \{(a,A),...\}</math> eine 12-elementige Teilmenge von <math> \mathfrak{p}\times\mathfrak{B} </math>. 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 [[Affine Ebene#Beispiele|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 <math>I</math> ist dann die [[Elementzeichen|Enthaltenseinsrelation]] <math>\in</math>. 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 <math>\subseteq </math> auffassen.
* 4) <math>\mathfrak{p}</math> sei die Menge der Ursprungsgeraden im euklidischen Raum, <math>\mathfrak{B}</math> die Menge der ''Ursprungsebenen''. Ein Punkt <math>p</math> inzidiere mit einem Block <math>G</math>, falls <math>p</math> in <math>G</math> enthalten ist. Die Inzidenzstruktur ist in diesem Fall eine [[projektive Ebene]].
* 5) <math>\mathfrak{p}</math> sei die Menge der Punkte der Einheitskugel im 3-dimensionalen euklidischen Raum, <math>\mathfrak{B}</math> die Menge der ''Kreise'' auf der Einheitskugel und <math>\in</math> die Inzidenzrelation. Die Inzidenzstruktur <math>\mathcal{I}=(\mathfrak{p},\mathfrak{B},\in)</math> 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 [[Endliche Geometrie|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 <math>\mathcal{I}_1 = (\mathfrak{p_1},\mathfrak{B_1},I_1)</math> und <math>\mathcal{I}_2 = (\mathfrak{p_2},\mathfrak{B_2},I_2)</math> Inzidenzstrukturen. Eine [[bijektiv]]e Abbildung <math>f\colon\; \mathfrak{p_1}\cup\mathfrak{B_1}\rightarrow \mathfrak{p_2}\cup\mathfrak{B_2}</math> heißt ''Isomorphismus'' von <math>\mathcal{I}_1</math> auf <math>\mathcal{I}_2</math>, wenn gilt:<ref name="BP12" />
# <math>f</math> bildet Punkte auf Punkte und Blöcke auf Blöcke ab und
# für alle Punkte <math>p</math> und Blöcke <math>B</math> von <math>\mathcal{I}_1</math> gilt: <math>p\mathrel{\ I_1\ }B \Leftrightarrow f(p)\mathrel{\ I_2\ } f(B).</math>

=== Einfache Inzidenzstruktur ===
Die Inzidenzstruktur <math>\mathcal{I} = (\mathfrak{p},\mathfrak{B},I)</math> heißt ''einfach'', wenn für beliebige Blöcke <math>B,C\in \mathfrak{B}</math> gilt:
:<math>\left( \forall p\in \mathfrak{p}\colon\; p\mathrel{\ I\ }B \Leftrightarrow p\mathrel{\ I\ }C\right) \Rightarrow B = C,</math>
wenn also alle Blöcke durch die mit ihnen inzidierenden Punkte vollständig bestimmt sind.
Gleichwertig dazu ist: <math>\mathcal{I}=(\mathfrak{p},\mathfrak{B},I)</math> ist einfach genau dann, wenn <math>\mathcal{I}</math> isomorph zu einer Inzidenzstruktur <math>\mathcal{I} = (\mathfrak{p}',\mathfrak{B}',\in)</math> ist, wobei <math>\mathfrak{B}'</math> eine Teilmenge der [[Potenzmenge]] <math>\mathcal{P}(\mathfrak{p}')</math> von <math>\mathfrak{p}'</math> ist.<ref name="BP12" />

=== Dualität ===
* Zu einer Inzidenzstruktur <math>\mathcal{I}=\left(\mathfrak{p},\mathfrak{B},I\right)</math> wird die ''duale Inzidenzstruktur'' <math>\mathcal{I}^D = \left(\mathfrak{p}^D,\mathfrak{B}^D,I^D\right)</math> so gebildet:
:<math>\mathfrak{p}^D = \mathfrak{B},\quad \mathfrak{B}^D = \mathfrak{p},\quad I^D = I^{-1} = \left\{(B,p)\mid (p,B)\in I\right\}.</math>
: Die duale Inzidenzstruktur <math>\mathcal{I}^D</math> entsteht also aus <math>\mathcal{I}</math>, indem man die Blöcke die Rolle der Punkte spielen lässt und umgekehrt. Natürlich gilt <math>\left(\mathcal{I}^D\right)^D = \mathcal{I}.</math>

* 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 <math>K</math> von Inzidenzstrukturen wird mit <math>K^D</math> die Klasse der dualen Inzidenzstrukturen bezeichnet.

* Eine ''konkrete'' Inzidenzstruktur <math>\mathcal{I}</math> heißt ''zu sich selbst dual'', wenn es einen Isomorphismus <math>\phi\colon\; \mathcal{I}\rightarrow \mathcal{I}^D</math> gibt. Mit anderen Worten: <math>\mathcal{I}</math> ist genau dann zu sich selbst dual, wenn das Dualitätsprinzip für die Klasse <math>\operatorname{\mathbf{ISO}}(\mathcal{I})</math> der zu <math>\mathcal{I}</math> 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 <math>B\in\mathfrak{B}</math> mindestens zwei verschiedene Punkte <math>p_1,p_2\in\mathfrak{p}</math> existieren, die nicht mit ''B'' inzidieren.
* Ist <math>\mathfrak{m}\subseteq\mathfrak{p}</math> eine Teilmenge der Punktmenge einer Inzidenzstruktur, dann wird die Menge aller Blöcke, die mit jedem Punkt dieser Teilmenge inzidiert, als <math>(\mathfrak{m})</math> notiert; ist die Inzidenzstruktur endlich, dann wird die Anzahl dieser Blöcke als <math>[\mathfrak{m}] = |(\mathfrak{m})|</math> notiert. Die Symbole <math>(\mathfrak{M})</math> und <math>[\mathfrak{M}]</math> sind entsprechend dual als Punktmengen bzw. deren Anzahl für Mengen von Blöcken <math>\mathfrak{M}\subseteq \mathfrak{B}</math> einer (endlichen) Inzidenzstruktur erklärt. Formal:
:: <math>(\mathfrak{m}) = \{B\in \mathfrak{B} \mid \forall p\in\mathfrak{m}\colon\; p\mathrel{\ I\ } B \},\quad
(\mathfrak{M}) = \{p\in \mathfrak{p} \mid \forall B\in\mathfrak{M}\colon\; p\mathrel{\ I\ } B \}.</math>
* Aus der Definition ergibt sich, dass <math>(\emptyset)</math> 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 {{Anker|Grad}} ===
Einer endlichen Inzidenzstruktur werden für <math>i\in \{0,1,\ldots, |\mathfrak{p}|\}</math> und <math>j\in \{0,1,\ldots, |\mathfrak{B}|\}</math> die folgenden Parameter zugeordnet:
:<math>b_i := \binom{|\mathfrak{p}|}{i}^{-1}\cdot \sum_{\mathfrak{m}\subseteq \mathfrak{p}\atop |\mathfrak{m}|=i} [\mathfrak{m}],\quad
v_j := \binom{|\mathfrak{B}|}{j}^{-1}\cdot \sum_{\mathfrak{M}\subseteq \mathfrak{B}\atop |\mathfrak{M}|=j} [\mathfrak{M}].</math>

Der Parameter <math>b_i</math> gibt also an, wie viele Blöcke ''im Durchschnitt'' mit <math>i</math> verschiedenen Punkten inzidieren und der Parameter <math>v_j,</math> wie viele Punkte im Durchschnitt auf <math>j</math> verschiedenen Blöcken zugleich liegen. Der Parameter <math>v = v_0</math> ist die Gesamtzahl der Punkte und <math>b = b_0</math> die Gesamtzahl der Blöcke der endlichen Inzidenzstruktur.

Darüber hinaus wird, vor allem im Zusammenhang mit [[Linearer Raum (Geometrie)|linearen Räumen]], der Begriff ''Grad'' definiert:<ref>{{Literatur |Autor=Klaus Metsch |Titel=Linear Spaces with Few Lines |Verlag=Springer |Ort=Berlin/Heidelberg/New York/London/Paris/Tokyo/Hong Kong/Barcelona/Budapest |Datum=1991 |ISBN=3-540-54720-7 |Seiten=1}}</ref>
* Der Grad <math>r_p</math> eines Punktes <math>p</math> ist die Anzahl der Blöcke, mit denen <math>p</math> inzidiert.
* Der Grad <math>d_B</math> eines Blockes bzw. einer Geraden <math>B</math> ist die Anzahl der Punkte, mit denen <math>B</math> inzidiert.

Damit ist <math>v_1</math> der Durchschnitt aller Grade von Punkten und <math>b_1</math> der Durchschnitt aller Grade von Blöcken.

=== Regularitätsbedingungen und Typen von endlichen Inzidenzstrukturen {{Anker|Taktische Konfiguration}} ===
Für eine endliche Inzidenzstruktur werden die folgenden ''Regularitätsbedingungen''<ref name="Dem61">Dembowski (1961)</ref> definiert, anhand derer diese Strukturen klassifiziert werden können:
:<math>(\mathrm{P}_i)</math> Je <math>i</math> verschiedene Punkte inzidieren mit genau <math>b_i > 0</math> Blöcken. Mit anderen Worten: Für alle <math>i</math>-elementigen Teilmengen <math>\mathfrak{m}\subseteq\mathfrak{p}</math> gilt <math>[\mathfrak{m}] = b_i > 0.</math>
:<math>(\mathrm{B}_j)</math> Je <math>j</math> verschiedene Blöcke inzidieren mit genau <math>v_j > 0</math> Punkten. Mit anderen Worten: Für alle <math>j</math>-elementigen Teilmengen <math>\mathfrak{M}\subseteq\mathfrak{B}</math> gilt <math>[\mathfrak{M}] = v_j > 0.</math>

* Eine endliche Inzidenzstruktur, die die Regularitätsbedingungen <math>(\mathrm{P}_1),\ldots, (\mathrm{P}_m)</math> und <math>(\mathrm{B}_1),\ldots, (\mathrm{B}_n)</math> erfüllt, aber weder die Bedingung <math>(\mathrm{P}_{m+1})</math> noch die Bedingung <math>(\mathrm{B}_{n+1}),</math> wird als Inzidenzstruktur vom Typ <math>(m,n)</math> bezeichnet.
* Eine endliche Inzidenzstruktur, die (mindestens) die Regularitätsbedingungen <math>(\mathrm{P}_1),(\mathrm{B}_1)</math> erfüllt, wird als ''taktische Konfiguration''<ref name="BP12" /> (nach Moore<ref>Moore (1896)</ref>) bezeichnet. Typische Beispiele sind die [[Verallgemeinertes Viereck|verallgemeinerten Vierecke]].
* Eine endliche Inzidenzstruktur, die <math>(\mathrm{P}_2)</math> mit dem Parameter <math>b_2=1</math> erfüllt, heißt [[Inzidenzgeometrie]].

=== Inzidenzmatrix ===
→ Der hier beschriebene Begriff ''Inzidenzmatrix'' für eine endliche Inzidenzstruktur kann als Verallgemeinerung des Begriffes [[Inzidenzmatrix#Definition|Inzidenzmatrix eines ungerichteten Graphen]] angesehen werden.

Eine endliche Inzidenzstruktur mit <math>v\geq 1</math> Punkten und <math>b\geq 1</math> Blöcken kann auch durch eine <math>v \times b</math>-[[Matrix (Mathematik)|Matrix]] repräsentiert werden. Dazu nummeriert man die Punkte von <math>1</math> bis <math>v</math> und die Blöcke von <math>1</math> bis <math>b</math> durch und trägt in die Matrix die Beziehungen der Punkte zu den Blöcken ein:

:<math>
a_{ij} := \begin{cases}
1, & \text{ falls } (p_i,B_j)\in I, \\
0, & \text{ sonst}.
\end{cases}
</math>
Die Matrix <math>A = (a_{ij})_{1\leq i\leq v;\;1\leq j\leq b}</math> heißt dann eine ''Inzidenzmatrix'' der endlichen Inzidenzstruktur.<ref>Beutelspacher (1982), S. 41.</ref>

Natürlich liefern verschiedene Nummerierungen der Punkt- und Blockmenge im Allgemeinen verschiedene Inzidenzmatrizen. Offenbar ist jede Matrix, deren Elemente nur <math>0</math> und <math>1</math> sind, Inzidenzmatrix einer geeigneten endlichen Inzidenzstruktur und diese ist durch die Inzidenzmatrix vollständig bestimmt.

Es werden, vor allem im Zusammenhang mit [[Hadamard-Matrix|Hadamard-Matrizen]] auch ''<math>(1,-1)</math>-Inzidenzmatrizen'' verwendet, bei denen die Einträge <math>0</math> in der oben beschriebenen Matrix durch <math>-1</math> ersetzt werden.<ref>Beth, Jungnickel, Lenz, I §9: Hadamard designs</ref>

=== Ableitung einer Inzidenzstruktur ===
Für eine endliche oder unendliche Inzidenzstruktur <math>\mathcal{I}=(\mathfrak{p},\mathfrak{B},I)</math> bezeichnet man für einen Punkt <math>x\in\mathfrak{p}</math> die nachfolgende definierte Struktur als ''Ableitung von <math>\mathcal{I}</math> nach <math>x</math>'' oder auch ''am Punkt <math>x</math> abgeleitete Inzidenzstruktur''<ref>englisch: ''derived structure at a point ''<math>x</math> (Beth, Jungnickel, Lenz, Definition I.9.8)</ref><ref name="BP4">Beutelspacher (1982), 4. Nichtexistenzsätze</ref>
:<math>\mathcal{I}_x = (\mathfrak{p}\setminus\{x\},(x),I_{\mathrm{ind}}).</math>
Die Ableitung nach <math>x</math> besteht also aus allen Punkten außer <math>x</math> als Punktmenge <math>\mathfrak{p}_x=\mathfrak{p}\setminus\{x\},</math> den Blöcken durch <math>x</math> als Blockmenge <math>\mathfrak{B}_x = (x) = \{B\in \mathfrak{B} \mid x\mathrel{\ I\ } B\}</math> mit der ''induzierten Inzidenz'', <math>I_{\mathrm{ind}} = I\cap (\mathfrak{p}_x\times \mathfrak{B}_x).</math>
In diesem Fall bezeichnet man <math>\mathcal{I}</math> als ''Erweiterung'' von <math>\mathcal{I}_x.</math> 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 [[Blockplan|Blockplänen]] mit bestimmten Parametern auf die gewisser größerer Blockpläne geschlossen wird.<ref name="BP4" />

Wie sich die Ableitung auf die Parameter spezieller Inzidenzstrukturen auswirken kann, ist beispielhaft im Artikel [[Wittscher Blockplan]], dort insbesondere im Abschnitt [[Wittscher Blockplan#Inzidenzparameter der Wittschen Blockpläne|Inzidenzparameter der Wittschen Blockpläne]] dargestellt.

==== Beispiel ====
Ist die Inzidenzstruktur <math>\mathcal{I} = (\mathfrak{p},\mathfrak{B},I)</math> eine ''Möbius-Ebene'', so ist die Ableitung in jedem Punkt eine ''affine Ebene'' und damit eine einfachere Struktur (s. [[Möbius-Ebene#Die Axiome einer Möbius-Ebene|Möbius-Ebene]]).

== Eigenschaften ==
=== Dualitätsprinzip ===
* Ist <math>A</math> eine Aussage, die für alle Inzidenzstrukturen einer Klasse <math>K</math> gilt, so gilt die duale Aussage <math>A^D</math> für alle Inzidenzstrukturen aus <math>K^D.</math>
* Ist für eine Klasse <math>K</math> von Inzidenzstrukturen <math>K = K^D</math>, so sagt man „für <math>K</math> gilt das Dualitätsprinzip“. Dann ist für jede Aussage <math>A,</math> die für alle Inzidenzstrukturen aus <math>K</math> zutrifft, auch <math>A^D</math> 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 [[Projektive Ebene|projektiven Ebenen]],
* der projektiven Ebenen der [[Klassifikation projektiver Ebenen|Lenz-Klasse VII]] (das sind genau die [[Satz von Desargues|desarguesschen projektiven Ebenen]]),
* der endlichen Inzidenzstrukturen, deren Inzidenzmatrix als [[symmetrische Matrix]] gewählt werden kann.
Die beiden zuletzt genannten Klassen enthalten ausschließlich ''zu sich selbst duale'' Strukturen. Daher gilt hier das Dualitätsprinzip in seiner verschärften Form: Zu jeder Aussage, die in einer dieser Strukturen gilt, trifft die duale Aussage ''in derselben Struktur'' zu.<ref>Für die desarguesschen Ebenen: {{Literatur |Autor=Albrecht Beutelspacher, Ute Rosenbaum |Titel=Projektive Geometrie |TitelErg=Von den Grundlagen bis zu den Anwendungen |Reihe=Vieweg Studium: Aufbaukurs Mathematik |Auflage=2., durchgesehene und erweiterte |Verlag=Vieweg |Ort=Wiesbaden |Datum=2004 |ISBN=3-528-17241-X |Online=[http://d-nb.info/972794298/03 Inhaltsverzeichnis] |Abruf=2013-08-10}}</ref>

==== Gegenbeispiele ====
Das Dualitätsprinzip gilt ''nicht'' für die Klasse
* der Inzidenzstrukturen mit endlicher Punktmenge,
* der einfachen Inzidenzstrukturen,
* der ausgearteten Inzidenzstrukturen,
* der Inzidenzstrukturen, in denen jeder Punkt mit <math>m</math> Blöcken und jeder Block mit <math>n</math> Punkten inzidiert, es sei denn, es ist <math>m = n</math>,
* der [[Affine Ebene|affinen Ebenen]],
* der projektiven Ebenen der Lenz-Klasse IVa.

=== Beziehungen zwischen den Parametern ===
Im Folgenden ist <math>\mathcal{I} = (\mathfrak{p},\mathfrak{B},I)</math> eine endliche Inzidenzstruktur. Dann gilt nach dem ''Prinzip der doppelten Abzählung'':<ref>Diese Formel beruht darauf, dass auf beiden Seiten der Gleichung die Anzahl <math>|I|</math> aller Inzidenzen steht. Links sortiert nach den an der Inzidenz beteiligten ''Punkten'' und rechts nach den beteiligten ''Blöcken'', Beutelspacher (1982), Lemma 1.2.3</ref>
* <math>\sum_{p\in\mathfrak{p}} [p] = \sum_{B\in\mathfrak{B}} [B],</math>
* Das Prinzip der doppelten Abzählung durch Parameter ausgedrückt lautet: <math>v_0\cdot b_1 = v_1\cdot b_0.</math>

Die folgenden beiden, zueinander dualen Gleichungen erlauben es, sämtliche Parameter einer endlichen Inzidenzstruktur zu berechnen, wenn die Anzahl der Blöcke <math>[p]</math> für jeden Punkt und die Anzahl der Punkte <math>[B]</math> für jeden Block bekannt sind:
* <math>\sum_{B\in\mathfrak{B}} \binom{[B]}{i} = \binom{v}{i}\cdot b_i{\;}</math> für alle <math>{\;}i\in \{0,1,\ldots, v\}.</math>
* <math>\sum_{p\in\mathfrak{p}} \binom{[p]}{j} = \binom{b}{j}\cdot v_j{\;}</math> für alle <math>{\;}j\in \{0,1,\ldots, b\}.</math>
* Erfüllt die Inzidenzstruktur die Regularitätsbedingung <math>(\mathrm{B}_1)</math>, das heißt, gilt <math>[B] = v_1 > 0</math> für jeden Block, dann vereinfacht sich die erste Formel zu <math>b_i = \binom{v}{i}^{-1}\cdot b\cdot \binom{v_1}{i}.</math>
* Erfüllt die Inzidenzstruktur die Regularitätsbedingung <math>(\mathrm{P}_1)</math>, das heißt, gilt <math>[p] = b_1 > 0</math> für jeden Punkt, dann vereinfacht sich die zweite Formel zu <math>v_j = \binom{b}{j}^{-1}\cdot v\cdot \binom{b_1}{j}.</math>

Die folgenden beiden, ebenfalls zueinander dualen Ungleichungen für beliebige endliche Inzidenzstrukturen wurden von ''Dembowski'' bewiesen:<ref name="Dem61" /><ref>Beutelspacher (1982), Hauptsatz 1.2.9</ref>
* <math>b_i\cdot (v_1-i) \leq b_{i+1}\cdot (v-i){\;}</math> für alle <math>{\;}i\in \{0,1,\ldots, v\}.</math>
* <math>v_j\cdot (b_1-j) \leq v_{j+1}\cdot (b-j){\;}</math> für alle <math>{\;}j\in \{0,1,\ldots, b\}.</math>
* Hat die Inzidenzstruktur den Typ <math>(m,n),\; m,n\geq 2</math> und ist <math>I\neq \mathfrak{p}\times \mathfrak{B}.</math> Dann gilt für alle nichtnegativen Zahlen <math>i\colon\; v_i = b_i</math>.<ref>Beachte, dass hier – für eine ausgeartete Inzidenzstruktur – auch <math>m>2</math> oder <math>n>2</math> vorkommen kann, Beutelspacher (1982), Korollar 1.3.3</ref>

=== Regularitätsbedingungen ===
* Aus der Gültigkeit von <math>(\mathrm{P}_m)</math> und <math>(\mathrm{B}_1)</math> folgt die Gültigkeit von <math>(\mathrm{P}_{m-1}),\ldots,(\mathrm{P}_1).</math>
* Aus der Gültigkeit von <math>(\mathrm{B}_n)</math> und <math>(\mathrm{P}_1)</math> folgt die Gültigkeit von <math>(\mathrm{B}_{n-1}),\ldots,(\mathrm{B}_1).</math>
* Ist <math>(m,n)</math> der Typ einer nichtausgearteten, endlichen Inzidenzstruktur, dann gilt <math>m\leq 1</math> oder <math>n\leq 1</math> oder <math>m = n = 2.</math><ref name="Dem61" />

=== Eigenschaften der Inzidenzstruktur anhand der Inzidenzmatrix ===
* Sind <math>\mathcal{I},\mathcal{J}</math> endliche Inzidenzstrukturen, die durch die Inzidenzmatrizen <math>A = (a_{ij})</math> bzw. <math>B = (b_{ij})</math> beschrieben werden können, dann sind diese Inzidenzstrukturen genau dann isomorph, wenn die beiden Matrizen vom gleichen Typ <math>v\times b,\; v,b\in \N</math> sind und eine Zeilenpermutation <math>\pi\in S_v</math> (<math>S_v</math> ist die [[symmetrische Gruppe]] auf <math>v</math> Elementen) sowie eine Spaltenpermutation <math>\rho\in S_b</math> existieren, mit denen <math>a_{\pi(i)\rho(j)} = b_{ij}</math> für <math>1\leq i\leq v,\; 1\leq j\leq b</math> gilt.
:* Insbesondere können zwei verschiedene Inzidenzmatrizen genau dann die gleiche Inzidenzstruktur beschreiben, wenn die eine durch solche Zeilen- und Spaltenpermutationen in die andere verwandelt werden kann.
* Eine endliche Inzidenzstruktur ist genau dann einfach, wenn keine zwei Spalten einer und damit jeder Inzidenzmatrix für die Struktur miteinander übereinstimmen.
* Eine endliche Inzidenzstruktur ist genau dann ausgeartet, wenn eine Spalte einer und damit jeder Inzidenzmatrix für die Struktur höchstens eine 0 enthält.
* Die duale einer endlichen Inzidenzstruktur mit Inzidenzmatrix ''A'' kann durch die [[Transponierte Matrix|transponierte]] Inzidenzmatrix <math>A^T</math> beschrieben werden.
:* Insbesondere ist eine endliche Inzidenzstruktur genau dann zu ihrer dualen Struktur isomorph, wenn ihre Inzidenz durch eine symmetrische Matrix beschrieben werden kann.

== Beispiele ==
* Eine ''triviale Rang 2-Geometrie'' (im Sinne der [[Buekenhout-Tits-Geometrie]]) besteht aus einer nichtleeren Punkt- und Blockmenge <math>\mathfrak{p},\mathfrak{B}</math>, mit der Inzidenzrelation <math>I = \mathfrak{p}\times\mathfrak{B}</math>. Zum Beispiel ist das ''Residuum'' einer bestimmten Gerade ''g'' in einem dreidimensionalen affinen oder projektiven Raum eine solche Inzidenzstruktur: Jeder Punkt auf der Gerade ''g'' (also jeder „Punkt“ der Punktmenge <math>\mathfrak{p}</math>) inzidiert mit jeder Ebene durch diese Gerade (also jedem „Block“ der Blockmenge <math>\mathfrak{B}</math>) und umgekehrt. Diese Inzidenzstrukturen sind ausgeartet und (falls Punkt- und Blockmenge jeweils mehr als ein Element enthalten) nicht einfach. Man beachte, dass solche in geometrischen Zusammenhängen auftretenden Inzidenzstrukturen im Allgemeinen keine Inzidenz''geometrien'' sind.
** Ist eine solche triviale Inzidenzstruktur endlich, <math>|\mathfrak{p}| = v\geq 2,\; |\mathfrak{B}| = b\geq 2</math> dann hat sie den Typ <math>(v,b).</math> Ihre Parameter sind <math>b = b_0 = b_1 = \cdots = b_v</math> und <math>v = v_0 = v_1 = \cdots = v_b.</math><ref> Es muss aber im Allgemeinen ''nicht'' <math>v = b</math> sein! Die Bedingung <math>I\neq \mathfrak{p}\times \mathfrak{B}</math> ist verletzt. Beutelspacher (1982)</ref>

* Die Inzidenzstruktur <math>(\{1,2,3\},\{\emptyset,\{1,2\},\{1,2,3\}\},\in)</math> ist nach Konstruktion einfach, ihre duale Inzidenzstruktur ist es nicht, denn die Punkte 1 und 2 inzidieren mit denselben Blöcken. Eine Inzidenzmatrix lautet:
:<math>\Bigl(\begin{smallmatrix} 0&1&1\\0&1&1\\0&0&1 \end{smallmatrix}\Bigr).</math>

* Die Inzidenzstruktur <math>(\{1,2,3\},\{\{3\}\},\in)</math> ist nach Konstruktion einfach. Sie ist nichtausgeartet, aber die duale Inzidenzstruktur ist ausgeartet und nicht einfach. Eine Inzidenzmatrix lautet:
:<math>\Bigl(\begin{smallmatrix} 0\\0\\1 \end{smallmatrix}\Bigr).</math>

* Eine Inzidenzstruktur <math>\mathcal{I} = (\mathfrak{p},\{\mathfrak{p}\},\in)</math>, bei der also alle Punkte mit dem einzigen Block inzidieren, ist einfach und ausgeartet. Ist die Punktmenge endlich und <math>m = |\mathfrak{p}|</math> die Anzahl ihrer Punkte, so ist <math>\mathcal{I}</math> ein [[schwach affiner Raum]] und hat den Typ <math>(m,1).</math>

* Eine endliche projektive Ebene ist eine nichtausgeartete Inzidenzstruktur vom Typ <math>(2,2).</math>

* Eine nichtausgeartete, endliche Inzidenzstruktur vom Typ <math>(t,n),\; t,n\geq 1,</math> ist ein <math>t-(v,k,\lambda)</math>-[[Blockplan]]. Parameter sind dann <math>v_0 = v,\; b_1 = k,\; b_t = \lambda.</math>

* Ein [[Netz (Diskrete Mathematik)|Netz]] ist stets eine Inzidenzstruktur vom Typ <math>(m,1),\; m\in \{1,2\}</math>. Genau dann, wenn <math>m = 2</math> ist, ist das Netz sogar eine [[affine Ebene]].

* Die Axiome eines [[Linearer Raum (Geometrie)|linearen Raumes]] <math>\mathcal{L} = (\mathfrak{p},\mathfrak{B},I)</math> lassen sich zum Teil durch eine Regularitätsbedingung und durch Forderungen an die Parameter der Inzidenzstruktur <math>\mathcal{L}</math> formulieren: Die Bedingung <math>(\mathrm{P}_2)</math> muss mit <math>b_2 = 1</math> erfüllt sein und es muss <math>b_0\geq 2</math> sein. Hinzu kommt die Forderung, dass für jeden Block (jede ''Gerade'') <math>B\in\mathfrak{B}\; [B]\geq 2</math> sein muss.
** Ein ''near pencil'' mit <math>v\geq 3</math> Punkten ist ein spezieller linearer Raum, er lässt sich als Inzidenzstruktur durch die Punktmenge <math>\mathfrak{p} = \{1,2,3,\ldots,v\}</math> und die Blockmenge <math>\mathfrak{B} = \{\{2,3,\ldots,v\},\; \{1,2\},\{1,3\},\ldots\{1,v\}\}</math> mit der Enthaltenrelation als Inzidenz beschreiben (vgl. [[Linearer Raum (Geometrie)#Beispiele]]). Ein near pencil ist einfach, ausgeartet und zu seiner dualen Struktur isomorph. Er erfüllt die Regularitätsbedingungen <math>(\mathrm{P}_2),(\mathrm{B}_2)</math> mit den Parametern <math>b_2 = v_2 = 1</math> aber (außer für <math>v = 3</math>) weder <math>(\mathrm{P}_1)</math> noch <math>(\mathrm{B}_1)</math>. Der near pencil mit vier Punkten hat zum Beispiel die Inzidenzmatrix
::<math>\biggl(\begin{smallmatrix} 0&1&1&1\\1&1&0&0\\1&0&1&0\\1&0&0&1 \end{smallmatrix}\biggr).</math>

* Jeder ungerichtete [[Graph (Graphentheorie)|Graph im Sinne der Graphentheorie]] kann als spezielle endliche Inzidenzstruktur angesehen werden, indem man die ''Knoten'' des Graphen als ''Punkte'' und die ''Kanten'' als ''Blöcke'' auffasst. Eine endliche Inzidenzstruktur ist genau dann ein ungerichteter Graph, wenn jeder Block mit genau zwei Punkten inzidiert, das heißt für eine Inzidenzmatrix: In jeder Spalte stehen genau zwei Einträge <math>1,</math> sonst nur <math>0.</math>

== Literatur ==
* {{Literatur |Autor=[[Thomas Beth]], [[Dieter Jungnickel]], [[Hanfried Lenz]] |Titel=Design Theory |Auflage=2. |Verlag=B.I. Wissenschaftsverlag |Ort=London / New York / New Rochelle / Melbourne / Sidney |Datum=1999 |ISBN=0-521-33334-2}}
* {{Literatur |Autor=[[Albrecht Beutelspacher]] |Titel=Einführung in die endliche Geometrie |TitelErg=I. Blockpläne |Verlag=B.I. Wissenschaftsverlag |Ort=Mannheim / Wien / Zürich |Datum=1982 |ISBN=3-411-01632-9 |Kapitel=Kapitel 1. Grundlagen}}
* {{Literatur |Autor=[[Peter Dembowski]] |Titel=Kombinatorische Eigenschaften endlicher Inzidenzstrukturen |Sammelwerk=Mathematische Zeitschrift |Band=75 |Nummer=1 |Datum=1961 |Seiten=256–270 |DOI=10.1007/BF01211024}}
* {{Literatur |Autor=[[Eliakim Hastings Moore]] |Titel=Tactical memoranda |Sammelwerk=American Journal of Mathematics |Band=18 |Nummer=3 |Datum=1896 |Seiten=264–290 |JSTOR=2369797}}

== Einzelnachweise und Anmerkungen ==
<references />

[[Kategorie:Inzidenzstruktur| ]]
[[Kategorie:Endliche Geometrie]]
[[Kategorie:Synthetische Geometrie]]

Inzidenzstruktur - Versionsgeschichte

imported>PhiRho~dewiki: /* Definition */ Komma ergänzt