Past exam of the computer science course of the University of Oxford / 2023 / Combinatorial optimisation / 2 / a / Solution

A matroid is a pair $(X,\mathcal{I})$, where $X$ is a finite ground set and $\mathcal{I}\subseteq 2^X$ is its collection of matroid independent sets, satisfying the matroid independence axioms:

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.