3

I'm working though Welsh's Matroid Theory work, and he very casually mentions matroid isomorphisms in the first chapter but I don't think I like his statement. He says that two matroids $M_1=(S_1,I_1)$ and $M_2 = (S_2,I_2)$ are isomorphic if there exists a bijection $\phi : \mathbf{S_1} \rightarrow \mathbf{S_2}$ (emphasis mine) that preserves independence, but I don't think this definition works out quite right. I think it should be from $\phi : \mathcal{P}(S_1) \rightarrow \mathcal{P}(S_2)$ where $\mathcal{P}(S)$ is the power set of $S$, because subsets larger than just individual elements of $S$ should be mapped to the target matroid in order to compare independence. In other words:

Two matroids $M_1=(S_1,I_1)$ and $M_2=(S_2,I_2)$ are isomorphic if there exists $\phi: \mathcal{P}(S_1) \rightarrow \mathcal{P}(S_2)$ such that $X \in I_1$ iff $\phi(X) \in I_2$.

Am I being too picky or is this a more accurate (or more careful) definition of a matroid isomorphism?

Thanks!

walkar
  • 3,844
  • 4
    When you biject elements, this induces a bijection on sets of elements. – vadim123 Dec 20 '14 at 06:03
  • 1
    So you're saying the definition $\phi: S_1 \rightarrow S_2$ extends naturally to $\phi : \mathcal{P}(S_1) \rightarrow \mathcal{P}(S_2)$? To me, it seems sort of backwards to present the definition in that way if we want our isomorphism to preserve independence, but independent sets are elements of the power set instead of elements of the ground set. That was sort of the point of the question. – walkar Dec 20 '14 at 07:28
  • 2
    On the contrary, it forces the natural bijection between the power sets. Your proposed definition includes the natural bijection, but also perhaps unnatural bijections that we don't want. – vadim123 Dec 20 '14 at 14:42

3 Answers3

6

It often happens in matroid theory that there are equivalent ways of expressing the same thing. You can think of an isomorphism as a map sending one independent set to another, or you may find it more convenient to say where the circuits map to instead. Either way, elements in one set land in another set, so you have to say where the elements map to.

I think it's generally better to think of an isomorphism as a map on elements rather than sets, because viewing it this way, the isomorphism is just an action of the symmetric group on the ground set. All you're really doing is relabeling the elements so they still fit into independent sets or circuits or whatever axiom system you're using, and structure is preserved.

Think of graph isomorphisms. If $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, which seems more natural to define an isomorphism $\phi$: letting $\phi$ be a map from one edge set to another, or defining $\phi$ on the powerset of the edge set?

NoName
  • 2,975
1

I believe under some axiom systems, your definition is actually strictly different from Welsh's.

https://mathoverflow.net/a/6594

This suggests to me that it could be possible to have your bijection without having Welsh's bijection in an appropriate axiom system. Allow me to consider infinite matroids which have slightly different axioms from the usual finite matroids. Consider $M=(E, \mathcal{P} (E))$ and $N=(F, \mathcal{P} (F))$ where $F$ is a set with strictly larger cardinality than $E$ such that there exists a bijection $\phi$ between $\mathcal{P} (F)$ and $\mathcal{P} (E)$. Then $\phi$ is a matroid isomorphism between $M$ and $N$ under your definition but there is no matroid isomorphism under Welsh's definition.

Community
  • 1
Patrick Tam
  • 443
1

Your definition of matroid isomorphism is too weak.

Under your definition, any two matroids with the same number of elements and the same number of independent sets will be isomorphic. Just choose any bijection $I_1\to I_2$ and extend it to a bijection $\mathcal P(S_1)\to\mathcal P(S_2)$ and you found your isomorphism.

This would probably declare wildly different matroids to be isomorphic.

M. Winter
  • 29,928