Inzidenzstruktur

Isomorphismen von Inzidenzstrukturen

Seien ${\displaystyle {\mathcal {I}}_{1}=({\mathfrak {p_{1}}},{\mathfrak {B_{1}}},I_{1})}$ und ${\displaystyle {\mathcal {I}}_{2}=({\mathfrak {p_{2}}},{\mathfrak {B_{2}}},I_{2})}$ Inzidenzstrukturen. Eine bijektive Abbildung ${\displaystyle f\colon \;{\mathfrak {p_{1}}}\cup {\mathfrak {B_{1}}}\rightarrow {\mathfrak {p_{2}}}\cup {\mathfrak {B_{2}}}}$ heißt Isomorphismus von ${\displaystyle {\mathcal {I}}_{1}}$ auf ${\displaystyle {\mathcal {I}}_{2}}$, wenn gilt:

1. ${\displaystyle f}$ bildet Punkte auf Punkte und Blöcke auf Blöcke ab und
2. für alle Punkte ${\displaystyle p}$ und Blöcke ${\displaystyle B}$ von ${\displaystyle {\mathcal {I}}_{1}}$ gilt: ${\displaystyle p{\mathrel {\ I_{1}\ }}B\Leftrightarrow f(p){\mathrel {\ I_{2}\ }}f(B).}$

Einfache Inzidenzstruktur

Die Inzidenzstruktur ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)}$ heißt einfach, wenn für beliebige Blöcke ${\displaystyle B,C\in {\mathfrak {B}}}$ gilt:

${\displaystyle \left(\forall p\in {\mathfrak {p}}\colon \;p{\mathrel {\ I\ }}B\Leftrightarrow p{\mathrel {\ I\ }}C\right)\Rightarrow B=C,}$

wenn also alle Blöcke durch die mit ihnen inzidierenden Punkte vollständig bestimmt sind. Gleichwertig dazu ist: ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)}$ ist einfach genau dann, wenn ${\displaystyle {\mathcal {I}}}$ isomorph zu einer Inzidenzstruktur ${\displaystyle {\mathcal {I}}=({\mathfrak {p}}',{\mathfrak {B}}',\in )}$ ist, wobei ${\displaystyle {\mathfrak {B}}'}$ eine Teilmenge der Potenzmenge ${\displaystyle {\mathcal {P}}({\mathfrak {p}}')}$ von ${\displaystyle {\mathfrak {p}}'}$ ist.

Dualität

• Zu einer Inzidenzstruktur ${\displaystyle {\mathcal {I}}=\left({\mathfrak {p}},{\mathfrak {B}},I\right)}$ wird die duale Inzidenzstruktur ${\displaystyle {\mathcal {I}}^{D}=\left({\mathfrak {p}}^{D},{\mathfrak {B}}^{D},I^{D}\right)}$ so gebildet:

${\displaystyle {\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\}.}$

Die duale Inzidenzstruktur ${\displaystyle {\mathcal {I}}^{D}}$ entsteht also aus ${\displaystyle {\mathcal {I}}}$, indem man die Blöcke die Rolle der Punkte spielen lässt und umgekehrt. Natürlich gilt ${\displaystyle \left({\mathcal {I}}^{D}\right)^{D}={\mathcal {I}}.}$

• 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 ${\displaystyle K}$ von Inzidenzstrukturen wird mit ${\displaystyle K^{D}}$ die Klasse der dualen Inzidenzstrukturen bezeichnet.

• Eine konkrete Inzidenzstruktur ${\displaystyle {\mathcal {I}}}$ heißt zu sich selbst dual, wenn es einen Isomorphismus ${\displaystyle \phi \colon \;{\mathcal {I}}\rightarrow {\mathcal {I}}^{D}}$ gibt. Mit anderen Worten: ${\displaystyle {\mathcal {I}}}$ ist genau dann zu sich selbst dual, wenn das Dualitätsprinzip für die Klasse ${\displaystyle \operatorname {\mathbf {ISO} } ({\mathcal {I}})}$ der zu ${\displaystyle {\mathcal {I}}}$ 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 ${\displaystyle B\in {\mathfrak {B}}}$ mindestens zwei verschiedene Punkte ${\displaystyle p_{1},p_{2}\in {\mathfrak {p}}}$ existieren, die nicht mit B inzidieren.
• Ist ${\displaystyle {\mathfrak {m}}\subseteq {\mathfrak {p}}}$ eine Teilmenge der Punktmenge einer Inzidenzstruktur, dann wird die Menge aller Blöcke, die mit jedem Punkt dieser Teilmenge inzidiert, als ${\displaystyle ({\mathfrak {m}})}$ notiert; ist die Inzidenzstruktur endlich, dann wird die Anzahl dieser Blöcke als ${\displaystyle [{\mathfrak {m}}]=|({\mathfrak {m}})|}$ notiert. Die Symbole ${\displaystyle ({\mathfrak {M}})}$ und ${\displaystyle [{\mathfrak {M}}]}$ sind entsprechend dual als Punktmengen bzw. deren Anzahl für Mengen von Blöcken ${\displaystyle {\mathfrak {M}}\subseteq {\mathfrak {B}}}$ einer (endlichen) Inzidenzstruktur erklärt. Formal:

${\displaystyle ({\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\}.}$

• Aus der Definition ergibt sich, dass ${\displaystyle (\emptyset )}$ 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 ${\displaystyle i\in \{0,1,\ldots ,|{\mathfrak {p}}|\}}$ und ${\displaystyle j\in \{0,1,\ldots ,|{\mathfrak {B}}|\}}$ die folgenden Parameter zugeordnet:

${\displaystyle 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}}].}$

Der Parameter ${\displaystyle b_{i}}$ gibt also an, wie viele Blöcke im Durchschnitt mit ${\displaystyle i}$ verschiedenen Punkten inzidieren und der Parameter ${\displaystyle v_{j},}$ wie viele Punkte im Durchschnitt auf ${\displaystyle j}$ verschiedenen Blöcken zugleich liegen. Der Parameter ${\displaystyle v=v_{0}}$ ist die Gesamtzahl der Punkte und ${\displaystyle b=b_{0}}$ 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 ${\displaystyle r_{p}}$ eines Punktes ${\displaystyle p}$ ist die Anzahl der Blöcke, mit denen ${\displaystyle p}$ inzidiert.
• Der Grad ${\displaystyle d_{B}}$ eines Blockes bzw. einer Geraden ${\displaystyle B}$ ist die Anzahl der Punkte, mit denen ${\displaystyle B}$ inzidiert.

Damit ist ${\displaystyle v_{1}}$ der Durchschnitt aller Grade von Punkten und ${\displaystyle b_{1}}$ der Durchschnitt aller Grade von Blöcken.

Regularitätsbedingungen und Typen von endlichen Inzidenzstrukturen

Für eine endliche Inzidenzstruktur werden die folgenden Regularitätsbedingungen definiert, anhand derer diese Strukturen klassifiziert werden können:

${\displaystyle (\mathrm {P} _{i})}$ Je ${\displaystyle i}$ verschiedene Punkte inzidieren mit genau ${\displaystyle b_{i}>0}$ Blöcken. Mit anderen Worten: Für alle ${\displaystyle i}$-elementigen Teilmengen ${\displaystyle {\mathfrak {m}}\subseteq {\mathfrak {p}}}$ gilt ${\displaystyle [{\mathfrak {m}}]=b_{i}>0.}$

${\displaystyle (\mathrm {B} _{j})}$ Je ${\displaystyle j}$ verschiedene Blöcke inzidieren mit genau ${\displaystyle v_{j}>0}$ Punkten. Mit anderen Worten: Für alle ${\displaystyle j}$-elementigen Teilmengen ${\displaystyle {\mathfrak {M}}\subseteq {\mathfrak {B}}}$ gilt ${\displaystyle [{\mathfrak {M}}]=v_{j}>0.}$

• Eine endliche Inzidenzstruktur, die die Regularitätsbedingungen ${\displaystyle (\mathrm {P} _{1}),\ldots ,(\mathrm {P} _{m})}$ und ${\displaystyle (\mathrm {B} _{1}),\ldots ,(\mathrm {B} _{n})}$ erfüllt, aber weder die Bedingung ${\displaystyle (\mathrm {P} _{m+1})}$ noch die Bedingung ${\displaystyle (\mathrm {B} _{n+1}),}$ wird als Inzidenzstruktur vom Typ ${\displaystyle (m,n)}$ bezeichnet.
• Eine endliche Inzidenzstruktur, die (mindestens) die Regularitätsbedingungen ${\displaystyle (\mathrm {P} _{1}),(\mathrm {B} _{1})}$ erfüllt, wird als taktische Konfiguration (nach Moore) bezeichnet. Typische Beispiele sind die verallgemeinerten Vierecke.
• Eine endliche Inzidenzstruktur, die ${\displaystyle (\mathrm {P} _{2})}$ mit dem Parameter ${\displaystyle b_{2}=1}$ 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 ${\displaystyle v\geq 1}$ Punkten und ${\displaystyle b\geq 1}$ Blöcken kann auch durch eine ${\displaystyle v\times b}$-Matrix repräsentiert werden. Dazu nummeriert man die Punkte von ${\displaystyle 1}$ bis ${\displaystyle v}$ und die Blöcke von ${\displaystyle 1}$ bis ${\displaystyle b}$ durch und trägt in die Matrix die Beziehungen der Punkte zu den Blöcken ein:

${\displaystyle a_{ij}:={\begin{cases}1,&{\text{ falls }}(p_{i},B_{j})\in I,\\0,&{\text{ sonst}}.\end{cases}}}$

Die Matrix ${\displaystyle A=(a_{ij})_{1\leq i\leq v;\;1\leq j\leq b}}$ heißt dann eine Inzidenzmatrix der endlichen Inzidenzstruktur.

Natürlich liefern verschiedene Nummerierungen der Punkt- und Blockmenge im Allgemeinen verschiedene Inzidenzmatrizen. Offenbar ist jede Matrix, deren Elemente nur ${\displaystyle 0}$ und ${\displaystyle 1}$ 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 ${\displaystyle (1,-1)}$-Inzidenzmatrizen verwendet, bei denen die Einträge ${\displaystyle 0}$ in der oben beschriebenen Matrix durch ${\displaystyle -1}$ ersetzt werden.

Ableitung einer Inzidenzstruktur

Für eine endliche oder unendliche Inzidenzstruktur ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)}$ bezeichnet man für einen Punkt ${\displaystyle x\in {\mathfrak {p}}}$ die nachfolgende definierte Struktur als Ableitung von ${\displaystyle {\mathcal {I}}}$ nach ${\displaystyle x}$ oder auch am Punkt ${\displaystyle x}$ abgeleitete Inzidenzstruktur

${\displaystyle {\mathcal {I}}_{x}=({\mathfrak {p}}\setminus \{x\},(x),I_{\mathrm {ind} }).}$

Die Ableitung nach ${\displaystyle x}$ besteht also aus allen Punkten außer ${\displaystyle x}$ als Punktmenge ${\displaystyle {\mathfrak {p}}_{x}={\mathfrak {p}}\setminus \{x\},}$ den Blöcken durch ${\displaystyle x}$ als Blockmenge ${\displaystyle {\mathfrak {B}}_{x}=(x)=\{B\in {\mathfrak {B}}\mid x{\mathrel {\ I\ }}B\}}$ mit der induzierten Inzidenz, ${\displaystyle I_{\mathrm {ind} }=I\cap ({\mathfrak {p}}_{x}\times {\mathfrak {B}}_{x}).}$ In diesem Fall bezeichnet man ${\displaystyle {\mathcal {I}}}$ als Erweiterung von ${\displaystyle {\mathcal {I}}_{x}.}$ 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.

Dualitätsprinzip

• Ist ${\displaystyle A}$ eine Aussage, die für alle Inzidenzstrukturen einer Klasse ${\displaystyle K}$ gilt, so gilt die duale Aussage ${\displaystyle A^{D}}$ für alle Inzidenzstrukturen aus ${\displaystyle K^{D}.}$
• Ist für eine Klasse ${\displaystyle K}$ von Inzidenzstrukturen ${\displaystyle K=K^{D}}$, so sagt man „für ${\displaystyle K}$ gilt das Dualitätsprinzip“. Dann ist für jede Aussage ${\displaystyle A,}$ die für alle Inzidenzstrukturen aus ${\displaystyle K}$ zutrifft, auch ${\displaystyle A^{D}}$ für alle diese Inzidenzstrukturen richtig.

Beziehungen zwischen den Parametern

Im Folgenden ist ${\displaystyle {\mathcal {I}}=({\mathfrak {p}},{\mathfrak {B}},I)}$ eine endliche Inzidenzstruktur. Dann gilt nach dem Prinzip der doppelten Abzählung:

• ${\displaystyle \sum _{p\in {\mathfrak {p}}}[p]=\sum _{B\in {\mathfrak {B}}}[B],}$
• Das Prinzip der doppelten Abzählung durch Parameter ausgedrückt lautet: ${\displaystyle v_{0}\cdot b_{1}=v_{1}\cdot b_{0}.}$

Die folgenden beiden, zueinander dualen Gleichungen erlauben es, sämtliche Parameter einer endlichen Inzidenzstruktur zu berechnen, wenn die Anzahl der Blöcke ${\displaystyle [p]}$ für jeden Punkt und die Anzahl der Punkte ${\displaystyle [B]}$ für jeden Block bekannt sind:

• ${\displaystyle \sum _{B\in {\mathfrak {B}}}{\binom {[B]}{i}}={\binom {v}{i}}\cdot b_{i}{\;}}$ für alle ${\displaystyle {\;}i\in \{0,1,\ldots ,v\}.}$
• ${\displaystyle \sum _{p\in {\mathfrak {p}}}{\binom {[p]}{j}}={\binom {b}{j}}\cdot v_{j}{\;}}$ für alle ${\displaystyle {\;}j\in \{0,1,\ldots ,b\}.}$
• Erfüllt die Inzidenzstruktur die Regularitätsbedingung ${\displaystyle (\mathrm {B} _{1})}$, das heißt, gilt ${\displaystyle [B]=v_{1}>0}$ für jeden Block, dann vereinfacht sich die erste Formel zu ${\displaystyle b_{i}={\binom {v}{i}}^{-1}\cdot b\cdot {\binom {v_{1}}{i}}.}$
• Erfüllt die Inzidenzstruktur die Regularitätsbedingung ${\displaystyle (\mathrm {P} _{1})}$, das heißt, gilt ${\displaystyle [p]=b_{1}>0}$ für jeden Punkt, dann vereinfacht sich die zweite Formel zu ${\displaystyle v_{j}={\binom {b}{j}}^{-1}\cdot v\cdot {\binom {b_{1}}{j}}.}$

Die folgenden beiden, ebenfalls zueinander dualen Ungleichungen für beliebige endliche Inzidenzstrukturen wurden von Dembowski bewiesen:

• ${\displaystyle b_{i}\cdot (v_{1}-i)\leq b_{i+1}\cdot (v-i){\;}}$ für alle ${\displaystyle {\;}i\in \{0,1,\ldots ,v\}.}$
• ${\displaystyle v_{j}\cdot (b_{1}-j)\leq v_{j+1}\cdot (b-j){\;}}$ für alle ${\displaystyle {\;}j\in \{0,1,\ldots ,b\}.}$
• Hat die Inzidenzstruktur den Typ ${\displaystyle (m,n),\;m,n\geq 2}$ und ist ${\displaystyle I\neq {\mathfrak {p}}\times {\mathfrak {B}}.}$ Dann gilt für alle nichtnegativen Zahlen ${\displaystyle i\colon \;v_{i}=b_{i}}$.

Regularitätsbedingungen

• Aus der Gültigkeit von ${\displaystyle (\mathrm {P} _{m})}$ und ${\displaystyle (\mathrm {B} _{1})}$ folgt die Gültigkeit von ${\displaystyle (\mathrm {P} _{m-1}),\ldots ,(\mathrm {P} _{1}).}$
• Aus der Gültigkeit von ${\displaystyle (\mathrm {B} _{n})}$ und ${\displaystyle (\mathrm {P} _{1})}$ folgt die Gültigkeit von ${\displaystyle (\mathrm {B} _{n-1}),\ldots ,(\mathrm {B} _{1}).}$
• Ist ${\displaystyle (m,n)}$ der Typ einer nichtausgearteten, endlichen Inzidenzstruktur, dann gilt ${\displaystyle m\leq 1}$ oder ${\displaystyle n\leq 1}$ oder ${\displaystyle m=n=2.}$

Eigenschaften der Inzidenzstruktur anhand der Inzidenzmatrix

• Sind ${\displaystyle {\mathcal {I}},{\mathcal {J}}}$ endliche Inzidenzstrukturen, die durch die Inzidenzmatrizen ${\displaystyle A=(a_{ij})}$ bzw. ${\displaystyle B=(b_{ij})}$ beschrieben werden können, dann sind diese Inzidenzstrukturen genau dann isomorph, wenn die beiden Matrizen vom gleichen Typ ${\displaystyle v\times b,\;v,b\in \mathbb {N} }$ sind und eine Zeilenpermutation ${\displaystyle \pi \in S_{v}}$ (${\displaystyle S_{v}}$ ist die symmetrische Gruppe auf ${\displaystyle v}$ Elementen) sowie eine Spaltenpermutation ${\displaystyle \rho \in S_{b}}$ existieren, mit denen ${\displaystyle a_{\pi (i)\rho (j)}=b_{ij}}$ für ${\displaystyle 1\leq i\leq v,\;1\leq j\leq b}$ 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 Inzidenzmatrix ${\displaystyle A^{T}}$ beschrieben werden.

• Insbesondere ist eine endliche Inzidenzstruktur genau dann zu ihrer dualen Struktur isomorph, wenn ihre Inzidenz durch eine symmetrische Matrix beschrieben werden kann.