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

The rank of a matroid on a subset $A\subseteq X$ isThe matroid independence axioms imply that every maximal matroid independent set in $A$ has this cardinality. We write $A+x=A\cup \{x\}$, as in the source. Directly from the definition,For the last upper bound, deleting $x$ from any matroid independent set in $A+x$ leaves an independent subset of $A$.

If $x\in Y$, then $Y+x=Y$, so $r(Y+x)=r(Y)$. By the definition of the closure of a matroid, $x\in \sigma (Y)$. Hence $Y\subseteq \sigma (Y)$.

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

Since $Y$ is a maximal matroid independent set in $Z$, augmentation gives $r(Y)=|Y|=r(Z)$. For any $x\in X$, the rank of a matroid of $Z+x$ equals that of $Y+x$. Indeed, if $x\notin Z$, either $Y+x$ is independent and has the largest possible size $|Y|+1$, or it is dependent and $Y$ is still maximal in $Z+x$: no element of $Z\setminus Y$ can be added, and neither can $x$. If $x\in Z$, both ranks are simply $|Y|$.

Consequently $r(Y+x)=r(Y)$ if and only if $r(Z+x)=r(Z)$, which proves $\sigma (Y)=\sigma (Z)$ for the closure of a matroid.

Choose a maximal matroid independent set $B\subseteq Y$. Its cardinality is $r(Y)=r(Z)$, so it is also maximal in $Z$. Apply (iv) first inside $Y$ and then inside $Z$:This proves that nested subsets of equal rank of a matroid have the same closure of a matroid.

List $\sigma (Y)\setminus Y=\{x_1,\dots ,x_m\}$ and put $Y_j=Y\cup \{x_1,\dots ,x_j\}$. Each $x_j\in \sigma (Y)$ also belongs to $\sigma (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 yieldsIn particular, collecting all elements that individually fail to increase the rank of a matroid does not create a collective increase.

By (ii), $Y\subseteq \sigma (Y)$, and by (vi) these subsets have equal rank of a matroid. Apply (v) to this pair to obtainThus the closure of a matroid is an idempotent function.

Write $r(Y)=r$. Since $y\notin \sigma (Y)$, the one-element increment bound gives $r(Y+y)=r+1$. Since $y\in \sigma (Y+x)$,But $Y+y\subseteq Y+x+y$ gives the reverse lower bound $r(Y+x+y)\ge r(Y+y)=r+1$. Hence $r(Y+x+y)=r(Y+y)$, which is precisely $x\in \sigma (Y+y)$. This is the matroid closure exchange property; it follows from one-element rank of a matroid increments and does not require exchanging an entire matroid basis.