A matroid M is a finite set S and a collection I of subsets of S (called independent sets) such that the following axioms are satisfied:

- (I1) ∅ ∈ I
- (I2) If X ∈ I and Y ⊆ X, then Y ∈ I.
- (I3) If U and V are members of I with |U| = |V| + 1, then there exists x ∈ U\V such that V ∪ x ∈ I.

Return to the homepage.