Unabhängigkeitssystem

Ist ein Mengensystem $(E,\mathcal{I})$ wobei $\mathcal{I}$ eine Teilmenge der Potenzmenge der Menge $E$ ist. Die folgenden Axiome müssen erfüllt sein:

• (I1) Die leere Menge ist in $\mathcal{I}$
• (I2) Wenn $I_2$ in $\mathcal{I}$ ist, dann ist auch eine Teilmenge $I_1$ von $I_2$ in $\mathcal{I}$ enthalten

Die Teilmengen von $E$, die in $\mathcal{I}$ enthalten sind, heißen unabhängig und alle übrigen Teilmengen von $E$ heißen abhängig.

Einige andere Mengensysteme sind mit dem Unabhängigkeitssystem verbunden:

• Kreissystem
• Basissystem

Eine spezielle Klasse der Unabhängigkeitssysteme ist das Matroid.

Andere Axiome:

Kreisaxiome Basisaxiome

Dualität von Matroiden

Greedy-Max für Unabhängigkeitssysteme

Schnitt von Unabhängigkeitssystemen und Matroiden.

Matroid-Intersektions-Problem