Incidenzstrukturen

Incidenzstrukturen sind in der Mathematik ein abstraktes Modell zur Beschreibung von Beziehungen zwischen zwei Arten von Objekten. Eine Incidenzstruktur besteht aus einer Punktmenge P, einer Blockmenge B und einer Inzidenzrelation I subseteq P × B, wobei p I B bedeutet, dass der Punkt p auf dem Block B liegt. Man spricht vom Tripel (P, B, I).

In der Praxis werden häufig folgende Größen verwendet: v = |P|, b = |B|, k(p) = Anzahl der Blöcke, die den Punkt p enthalten, und r(B) = Anzahl der Punkte, die auf dem Block B liegen. Oft ist der Blockgrad k konstant (k(p) = k für alle p) und der Punktgrad r konstant (r(B) = r für alle B). Strukturen, bei denen sowohl k als auch r konstant sind, heißen regulär. Legt man zusätzlich fest, dass zwei verschiedene Punkte auf höchstens einem gemeinsamen Block liegen, erhält man eine lineare Inzidenzstruktur. Eine symmetrische Struktur besitzt v = b und r = k.

Beispiele und Verbindungen: Ein endliches projektives Ebeneordner ist eine Inzidenzstruktur mit v = q^2 + q + 1, b = q^2 + q + 1, k = q + 1 und r = q + 1, wobei q eine Potenz einer Primzahl ist. Die endliche affine Ebene ordnet jedem Punkt q Linien zu, wobei k = q und r = q + 1 gilt. In der Designtheorie nennt man besondere Fälle Balanced Incomplete Block Designs (BIBD) mit Parametern (v, b, r, k, lambda), die vr = bk und lambda (v − 1) = r (k − 1) erfüllen.

Darstellungen und Anwendungen: Die Inzidenzmatrix N mit N[p,B] = 1 bei Inzidenz und 0 sonst dient der algebraischen Analyse; Incidence-Graphen liefern bipartite Graphen. Einsatzgebiete umfassen Entwurf stabiler Experimente, Codierungstheorie und Netzwerkdesign.