How to prove two matroids are equal?

205 Views Asked by At

One of my homework problem is to prove $(M^*)^*=M$, given $M=(S,\mathcal{I})$ is a matroid, i.e. dual of a dual matroid is itself.

My confusion is what is needed to prove the equality, in general. Is it good enough to say two matroids have same ground sets and their collections of independent sets are equivalent? Or what routine should I follow? Such as two directions of inclusive relation, any base in one matroid is a base in another matroid or something.

For example in this exercise, suppose I can apply the statement that the dual matroid of a matroid is a matroid, i.e. $M^*$ here. So then $(M^*)^*$ is a matroid immediately. Since the dual doesn't change the ground set so I don't need to worry about that. For independent set collection, $\mathcal{I}^*=\{A\subseteq S: S\backslash A\in \mathcal{I}\}$, then I can say $(\mathcal{I}^*)^*=\{A\subseteq S: S\backslash (S\backslash A)\in \mathcal{I}\}=\mathcal{I}$. Thus the two are equal.

1

There are 1 best solutions below

1
On BEST ANSWER

It is certainly enough to show that the collections of independent sets are the same.

Since a matroid is also determined by its bases you could show they are equal by showing they have exactly the same bases. This may be easier if you know the bases of the dual matroid in terms of those of the original.