 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2023/combinatorial-optimisation/2/a/solution

(X, I)

, where

X

is a finite ground set and

I \subseteq 2^{X}

$\emptyset \in I$ .
If $I \in I$ and $J \subseteq I$ , then $J \in I$ .
If $I, J \in I$ and $∣ I ∣ < ∣ J ∣$ , some $x \in J ∖ I$ satisfies $I \cup {x} \in I$ .

The last axiom is augmentation. In particular, every maximal matroid independent set within a given subset has maximum cardinality there: otherwise augmentation would enlarge it.

 New to topics? Read the docs here!