Inzidenzstruktur

Mathematischer Begriff, Verallgemeinerung der Euklidischen Ebene

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.

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

Bearbeiten

Eine Inzidenzstruktur[1] 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

 [2]

Für   schreibt man   und sagt, dass der Punkt   mit dem Block   inzidiert.

Die Relation   heißt in diesem Zusammenhang Inzidenzrelation.

Beispiele

Bearbeiten
  • 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

Bearbeiten

Isomorphismen von Inzidenzstrukturen

Bearbeiten

Seien   und   Inzidenzstrukturen. Eine bijektive Abbildung   heißt Isomorphismus von   auf  , wenn gilt:[1]

  1.   bildet Punkte auf Punkte und Blöcke auf Blöcke ab und
  2. für alle Punkte   und Blöcke   von   gilt:  

Einfache Inzidenzstruktur

Bearbeiten

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.[1]

Dualität

Bearbeiten
  • 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

Bearbeiten
  • 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

Bearbeiten

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:[3]

  • 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

Bearbeiten

Für eine endliche Inzidenzstruktur werden die folgenden Regularitätsbedingungen[4] 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[1] (nach Moore[5]) bezeichnet. Typische Beispiele sind die verallgemeinerten Vierecke.
  • Eine endliche Inzidenzstruktur, die   mit dem Parameter   erfüllt, heißt Inzidenzgeometrie.

Inzidenzmatrix

Bearbeiten

→ 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.[6]

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.[7]

Ableitung einer Inzidenzstruktur

Bearbeiten

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 Inzidenzstruktur[8][9]

 

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.[9]

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

Bearbeiten

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

Bearbeiten

Dualitätsprinzip

Bearbeiten
  • 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

Bearbeiten

Das Dualitätsprinzip gilt für die Klasse

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.[10]

Gegenbeispiele

Bearbeiten

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   Blöcken und jeder Block mit   Punkten inzidiert, es sei denn, es ist  ,
  • der affinen Ebenen,
  • der projektiven Ebenen der Lenz-Klasse IVa.

Beziehungen zwischen den Parametern

Bearbeiten

Im Folgenden ist   eine endliche Inzidenzstruktur. Dann gilt nach dem Prinzip der doppelten Abzählung:[11]

  •  
  • Das Prinzip der doppelten Abzählung durch Parameter ausgedrückt lautet:  

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

  •   für alle  
  •   für alle  
  • Erfüllt die Inzidenzstruktur die Regularitätsbedingung  , das heißt, gilt   für jeden Block, dann vereinfacht sich die erste Formel zu  
  • Erfüllt die Inzidenzstruktur die Regularitätsbedingung  , das heißt, gilt   für jeden Punkt, dann vereinfacht sich die zweite Formel zu  

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

  •   für alle  
  •   für alle  
  • Hat die Inzidenzstruktur den Typ   und ist   Dann gilt für alle nichtnegativen Zahlen  .[13]

Regularitätsbedingungen

Bearbeiten
  • Aus der Gültigkeit von   und   folgt die Gültigkeit von  
  • Aus der Gültigkeit von   und   folgt die Gültigkeit von  
  • Ist   der Typ einer nichtausgearteten, endlichen Inzidenzstruktur, dann gilt   oder   oder  [4]

Eigenschaften der Inzidenzstruktur anhand der Inzidenzmatrix

Bearbeiten
  • Sind   endliche Inzidenzstrukturen, die durch die Inzidenzmatrizen   bzw.   beschrieben werden können, dann sind diese Inzidenzstrukturen genau dann isomorph, wenn die beiden Matrizen vom gleichen Typ   sind und eine Zeilenpermutation   (  ist die symmetrische Gruppe auf   Elementen) sowie eine Spaltenpermutation   existieren, mit denen   für   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   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

Bearbeiten
  • Eine triviale Rang 2-Geometrie (im Sinne der Buekenhout-Tits-Geometrie) besteht aus einer nichtleeren Punkt- und Blockmenge  , mit der Inzidenzrelation  . 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  ) inzidiert mit jeder Ebene durch diese Gerade (also jedem „Block“ der Blockmenge  ) 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 Inzidenzgeometrien sind.
    • Ist eine solche triviale Inzidenzstruktur endlich,   dann hat sie den Typ   Ihre Parameter sind   und  [14]
  • Die Inzidenzstruktur   ist nach Konstruktion einfach, ihre duale Inzidenzstruktur ist es nicht, denn die Punkte 1 und 2 inzidieren mit denselben Blöcken. Eine Inzidenzmatrix lautet:
 
  • Die Inzidenzstruktur   ist nach Konstruktion einfach. Sie ist nichtausgeartet, aber die duale Inzidenzstruktur ist ausgeartet und nicht einfach. Eine Inzidenzmatrix lautet:
 
  • Eine Inzidenzstruktur  , bei der also alle Punkte mit dem einzigen Block inzidieren, ist einfach und ausgeartet. Ist die Punktmenge endlich und   die Anzahl ihrer Punkte, so ist   ein schwach affiner Raum und hat den Typ  
  • Eine endliche projektive Ebene ist eine nichtausgeartete Inzidenzstruktur vom Typ  
  • Eine nichtausgeartete, endliche Inzidenzstruktur vom Typ   ist ein  -Blockplan. Parameter sind dann  
  • Ein Netz ist stets eine Inzidenzstruktur vom Typ  . Genau dann, wenn   ist, ist das Netz sogar eine affine Ebene.
  • Die Axiome eines linearen Raumes   lassen sich zum Teil durch eine Regularitätsbedingung und durch Forderungen an die Parameter der Inzidenzstruktur   formulieren: Die Bedingung   muss mit   erfüllt sein und es muss   sein. Hinzu kommt die Forderung, dass für jeden Block (jede Gerade)   sein muss.
    • Ein near pencil mit   Punkten ist ein spezieller linearer Raum, er lässt sich als Inzidenzstruktur durch die Punktmenge   und die Blockmenge   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   mit den Parametern   aber (außer für  ) weder   noch  . Der near pencil mit vier Punkten hat zum Beispiel die Inzidenzmatrix
 
  • Jeder ungerichtete 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   sonst nur  

Literatur

Bearbeiten

Einzelnachweise und Anmerkungen

Bearbeiten
  1. a b c d Beutelspacher (1982), Abschnitt 1.2 Inzidenzstrukturen
  2. 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:  .
  3. Klaus Metsch: Linear Spaces with Few Lines. Springer, Berlin/Heidelberg/New York/London/Paris/Tokyo/Hong Kong/Barcelona/Budapest 1991, ISBN 3-540-54720-7, S. 1.
  4. a b c Dembowski (1961)
  5. Moore (1896)
  6. Beutelspacher (1982), S. 41.
  7. Beth, Jungnickel, Lenz, I §9: Hadamard designs
  8. englisch: derived structure at a point   (Beth, Jungnickel, Lenz, Definition I.9.8)
  9. a b Beutelspacher (1982), 4. Nichtexistenzsätze
  10. Für die desarguesschen Ebenen: Albrecht Beutelspacher, Ute Rosenbaum: Projektive Geometrie. Von den Grundlagen bis zu den Anwendungen (= Vieweg Studium: Aufbaukurs Mathematik). 2., durchgesehene und erweiterte Auflage. Vieweg, Wiesbaden 2004, ISBN 3-528-17241-X (Inhaltsverzeichnis [abgerufen am 10. August 2013]).
  11. Diese Formel beruht darauf, dass auf beiden Seiten der Gleichung die Anzahl   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
  12. Beutelspacher (1982), Hauptsatz 1.2.9
  13. Beachte, dass hier – für eine ausgeartete Inzidenzstruktur – auch   oder   vorkommen kann, Beutelspacher (1982), Korollar 1.3.3
  14. Es muss aber im Allgemeinen nicht   sein! Die Bedingung   ist verletzt. Beutelspacher (1982)