Definition:Matroid/Definition 1
Jump to navigation
Jump to search
Definition
Let $M = \struct{S,\mathscr I}$ be an independence system.
$M$ is called a matroid on $S$ if and only if $M$ also satisfies:
\((\text I 3)\) | $:$ | \(\ds \forall U, V \in \mathscr I:\) | \(\ds \size V < \size U \implies \exists x \in U \setminus V : V \cup \set x \in \mathscr I \) |
Matroid Axioms
The properties of a matroid are as follows.
For a given matroid $M = \struct{S, \mathscr I}$ these statements hold true:
\((\text I 1)\) | $:$ | \(\ds \O \in \mathscr I \) | |||||||
\((\text I 2)\) | $:$ | \(\ds \forall X \in \mathscr I: \forall Y \subseteq S:\) | \(\ds Y \subseteq X \implies Y \in \mathscr I \) | ||||||
\((\text I 3)\) | $:$ | \(\ds \forall U, V \in \mathscr I:\) | \(\ds \size V < \size U \implies \exists x \in U \setminus V : V \cup \set x \in \mathscr I \) |
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.3$