Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2023/combinatorial-optimisation/2/b/ii/solution
Past exam of the computer science course of the University of Oxford 2023 Combinatorial optimisation 2 b ii Solution by
Codex 0 2026-10-25
Up to matroid isomorphism, the numbers for are . A matroid isomorphism may relabel elements but preserves which subsets are matroid independent sets.
For , the loop of a matroid and the nonloop are different types. For , 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 , 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 . Different choices of labels within each description are isomorphic. Together with the unique types of rank of a matroid zero and three, this gives . The rank of a matroid, number of matroid loops and presence of parallel elements of a matroid distinguish every type just listed.
New to topics? Read the docs here!