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

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.

On fixed labelled ground sets of cardinality $1,2,3$, the numbers of matroids are respectively $2,5,16$.

For one element, the element is either a loop of a matroid or a nonloop, giving two choices. For two elements, rank of a matroid zero and two each give one possibility. At rank of a matroid one, the nonloops form any nonempty subset, giving $2^2-1=3$ more possibilities: total $1+3+1=5$.

For three elements, classify by the total rank of a matroid. At rank of a matroid zero every element is a matroid loop; at rank of a matroid three every subset is a matroid independent set. At rank of a matroid one, choose any nonempty subset of nonloops; exactly the empty set and their singletons are matroid independent sets. This gives seven possibilities.

At rank of a matroid two, either exactly two elements are nonloops, giving three choices for the remaining loop of a matroid, or all three are nonloops. In the latter case, pairs that are matroid dependent sets define parallel elements of a matroid. There can be no such pair, giving the uniform matroid $U_{2,3}$, or exactly one such pair, giving three choices. There cannot be exactly two such pairs: if $\{a,b\}$ and $\{a,c\}$ were matroid dependent sets but $\{b,c\}$ a matroid independent set, augmentation from $\{a\}$ to $\{b,c\}$ would fail. If all three pairs were matroid dependent sets, the rank of a matroid would be one. Hence rank of a matroid two gives $3+1+3=7$ examples.

Every listed possibility satisfies augmentation: the only nontrivial comparison on three elements is from a singleton to a two-element matroid independent set, and with at most one two-element matroid dependent set at least one addition works. The total is therefore $1+7+7+1=16$.

Up to matroid isomorphism, the numbers for $n=1,2,3$ are $2,4,8$. A matroid isomorphism may relabel elements but preserves which subsets are matroid independent sets.

For $n=1$, the loop of a matroid and the nonloop are different types. For $n=2$, there is one type each at rank of a matroid zero and two, and two types at rank of a matroid one, distinguished by having one or two nonloops. Thus there are four.

For $n=3$, the seven labelled examples of rank of a matroid one reduce to three types, distinguished by having one, two or three nonloops. The seven labelled examples of rank of a matroid two also reduce to three types: one loop of a matroid and two independent elements; no matroid loops and one pair of parallel elements of a matroid; or the uniform matroid $U_{2,3}$. Different choices of labels within each description are isomorphic. Together with the unique types of rank of a matroid zero and three, this gives $1+3+3+1=8$. The rank of a matroid, number of matroid loops and presence of parallel elements of a matroid distinguish every type just listed.

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.