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

Table of contents
- Solution a

Solution

A matroid is a pair

(X, I)

, where

X

is a finite ground set and

I \subseteq 2^{X}

is its collection of matroid independent sets, satisfying the matroid independence axioms:

$\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.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version