7
$\begingroup$

Let $M$ be a matroid on (finite) ground set $E$ with $\mathcal B(M)$ as its set of bases and $\mathcal C(M)$ as its set of circuits.

If we consider the uniform matroid $U_{m,n}$ for $m,n \in \mathbb N$ with $m < n$, then we see that $\mathcal C(U_{m,n}) = \mathcal B(U_{m+1,n})$.

Question: Is there any other pair $(M_1, M_2)$ of matroids with $\mathcal C(M_1) = \mathcal B(M_2)$ that are not uniform?

$\endgroup$
2
$\begingroup$

Yes there are more pairs like that. We know we can specify a matroid by its set of circuits and bases.

So now let $$B=C=\{X\subset\{1,2,3\}| |X|=2\}$$ Now consider the matroids $$M_1=(\{1,2,3,4\},\text{bases}=B)$$ $$M_2=(\{1,2,3,4\},\text{circuits}=C)$$ So $M_1$ and $M_2$ both have underlying set $\{1,2,3,4\}$, and there bases resp circuits specified as above. These will not be uniform matroids, but by definition have the required property.

$\endgroup$
  • $\begingroup$ Again, a great example! Thank you very much for your insights. $\endgroup$ – Moritz Sep 9 '16 at 14:42
2
$\begingroup$

Claim: Given two loop-free matroids $M_1$ and $M_2$, $\mathcal{B}(M_{1}) =\mathcal{C}(M_2)$ if and only if $M_1$ and $M_2$ are both partition matroids with $M_1 = \bigoplus_{i = 1} ^nU_{r_i,n_i}$ and $M_2 =\bigoplus_{i = 1} ^n U_{r_i-1,n_i}$.

Since bases (respectively, circuits) of a direct sum of matroids are just the disjoint union of bases (respectively, circuits) of the summands, it's enough to prove the above claim in the case when $M_2$ is connected.

Claim: Let $M_2$ be connected. Then $\mathcal{B}(M_1)=\mathcal{C}(M_2)$ if and only if there exist $1<r<n$ such that $M_1 = U_{r,n}$ and $M_2 = U_{r-1,n}$.

The "if" direction follows directly from the definition of uniform matroids. To prove the "only if" direction first let $r$ be the rank of $M_1$. Then every circuit of $M_2$ has cardinality $r$ and so by connectivity $M_2$ has rank $r-1$. So by Exercise 1.3.4 in Oxley's Matroid Theory, $M_2$ is uniform. Say $M_2=U_{r-1,n}$. Then $B(M_1)$ is the set of all $r$ element sets of an $n$ element set and so $M_1=U_{r,n}$, proving the claim.

$\endgroup$
  • $\begingroup$ My original question was indeed inspired by Oxley's book. I have one remark: Let $r=2$. If I follow your inference, then the circuits of $M_2$ all have cardinality $2$. Consider a partition matroid (Oxley's book: p. 18, example 1.2.8): there all circuits also have cardinality $2$ but the rank of the partition matroid can be arbitrary large. Do you understand what I mean? $\endgroup$ – Moritz Nov 10 '16 at 17:57
  • $\begingroup$ I don't have my copy of Oxley on hand at the moment to check, but if I remember correctly a partition matroid is the direct sum of uniform matroids. Is that correct? $\endgroup$ – Aaron Dall Nov 10 '16 at 18:44
  • $\begingroup$ @Moritz: You're exactly right. I was assuming that the matroids in question were connected. I've edited the answer to take care of the disconnected case. $\endgroup$ – Aaron Dall Nov 10 '16 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.