Definition:Independence System
Jump to navigation
Jump to search
Definition
Let $S$ be a finite set.
Let $\mathscr F$ be a set of subsets of $S$ satisfying the independence system axioms:
\((\text I 1)\) | $:$ | \(\ds \O \in \mathscr F \) | |||||||
\((\text I 2)\) | $:$ | \(\ds \forall X \in \mathscr F: \forall Y \subseteq S:\) | \(\ds Y \subseteq X \implies Y \in \mathscr F \) |
The ordered pair $I = \struct {S, \mathscr F}$ is called an independence system on $S$.
Also known as
When the context is obvious, $I = \struct {S, \mathscr F}$ is simply called an independence system.
Sources
- 2018: Bernhard H. Korte and Jens Vygen: Combinatorial Optimization: Theory and Algorithms (6th ed.) Chapter $13$ Matroids $\S 13.1$ Independence Systems and Matroids, Definition $13.1$