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

We first justify the submodularity of matroid rank, which will also support later arguments. Choose a maximal matroid independent set $I_0$ in $A\cap B$, extend it to a maximal matroid independent set $I_A$ in $A$, and then to one $I_U$ in $A\cup B$. These extensions exist by successive additions, and their sizes are the respective values of the rank of a matroid. No element of $I_U\setminus I_A$ lies in $A$: such an element could have been added to $I_A$, contradicting maximality in $A$. Therefore $I_0\cup (I_U\setminus I_A)$ is an independent subset of $B$, givingNow let $Y\subseteq Z$ and $x\in \sigma (Y)$. If $x\in Z$, then $x\in \sigma (Z)$ by (ii). Otherwise apply submodularity of matroid rank to $Y+x$ and $Z$, whose intersection is $Y$:The monotonicity of the rank of a matroid supplies the opposite bound $r(Z+x)\ge r(Z)$, so equality holds. Thus $x\in \sigma (Z)$, proving $\sigma (Y)\subseteq \sigma (Z)$.