 Solution

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

List

σ (Y) ∖ Y = {x_{1}, \dots, x_{m}}

and put

Y_{j} = Y \cup {x_{1}, \dots, x_{j}}

. Each

x_{j} \in σ (Y)

also belongs to

σ (Y_{j - 1})

by (iii). Thus the definition of the closure of a matroid gives

r (Y_{j}) = r (Y_{j - 1})

at every step. Iteration yields

r (σ (Y)) = r (Y_{m}) = r (Y) .

In particular, collecting all elements that individually fail to increase the rank of a matroid does not create a collective increase.

 New to topics? Read the docs here!