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

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.