6
$\begingroup$

Let $M$ be a matroid with its dual matroid $M^*$. Moreover, $\mathcal C(M)$ denotes the set of circuits of $M$, and $\mathcal F(M)$ is the set of its flats.

Question: Is there a matroid with $\mathcal F(M) \subsetneq \mathcal F(M^*)$ or $\mathcal C(M) \subsetneq \mathcal C(M^*)$?

$\endgroup$
5
$\begingroup$

For the circuit question there's the trivial case $$M=(S,\mathcal{P}(M))$$ Then $$M^*=(S,\{\emptyset\})$$ and $ \mathcal C(M)=\emptyset$, $\mathcal C(M^*)=\{\{s\}| s\in S\}$, so trivially $\mathcal C(M)\subsetneq \mathcal C(M^*)$. Also, $\mathcal{F}(M)=\mathcal{P}(M)$ while $\mathcal{F}(M^*)=S$, so $\mathcal{F}(M^*)\subsetneq \mathcal{F}(M)$


Here is a less trivial example for circuits (will suppress some of the $\{\}$):

$$M=(\{1,2,3,4\},\{1,2,3,4,13,14,23,24,234,134,\emptyset\})$$ Then $$M^*=\{\{1,2,3,4\},\{1,2,\emptyset\}\}$$ and $\mathcal C(M)=\{12\}$ while $\mathcal C(M^*)=\{3,4,12\}$


here is a less trivial example for flats: $U_{k,n}$ denotes the uniform matroid on $n$ elements.

$$\mathcal F(U_{k,n})=\{X: |X|<k\} \cup \{X: |X|=n\}$$ $$\mathcal F(U_{k,n}^*)=\mathcal F(U_{n-k,n})=\{X:|X|<n-k\} \cup \{X: |X| = n\}$$ So if $k< n-k$ then $U_{k,n}$ satisfies $\mathcal F(U_{k,n})\subsetneq \mathcal F(U_{k,n}^*)$

$\endgroup$
  • $\begingroup$ Thank you for the excellent examples. I leave the question open until September 13 to see if someone comes up with an idea for $\mathcal F(M) \subsetneq \mathcal F(M^*)$. $\endgroup$ – Moritz Sep 8 '16 at 16:40
  • 2
    $\begingroup$ @Moritz see my edit. $\endgroup$ – user2520938 Sep 8 '16 at 18:11
  • $\begingroup$ Perfect! Thank you again. $\endgroup$ – Moritz Sep 8 '16 at 18:24
3
$\begingroup$

First we have some useful terminology. Let $M,N$ be matroids on a common ground set $E$. The identity map on $E$ extends to a map $M \to N$ and, if $\mathcal{\mathcal{F}(N)} \subseteq \mathcal{\mathcal{F}(M)}$, then this extension is called a strong map. Equivalently, $M \to N$ is a strong map if every circuit of $M$ is a union of circuits of $N$. If there is a strong map $M \to N$, then the pair $(M,N)$ is called a matroid perspective. Similarly, if every circuit of $M$ is a circuit of $N$, then $M \to N$ is a weak map. Note that every weak map is also a strong map.

Restated in this terminology, the question in the OP reads

Is there a matroid that is not identically self-dual and that has either a strong map or a weak map onto its dual.

Now let's generalize @user2520938's example where $M^* = \{[4],\{\emptyset, 1,2\}\}$. Note that $M^*|\{1,2\}$ is an identically self-dual matroid and both 3 and 4 are loops in $M^*$.

Let $N$ be any matroid obtained from an identically self-dual matroid by adding a finite number $k>0$ of loops. Then $N^* \to N$ is a weak map (and hence a strong map) onto its dual.

For an identically self-dual matroid $M$ let $N = M \cup L$ where $L$ is a finite nonempty collection of loops. Then $N^*$ is a free extension of $M^*$ consisting of at least $|L|$ coloops. We then have $$\mathcal{C}(N^*) = \mathcal{C}(M^*) = \mathcal{C}(M) \subsetneq \mathcal{C}(M) \cup L = \mathcal{C}(N),$$ as desired.

This gives a large number of examples to the question in the OP, every one of which is slightly unsatisfying due to the triviality of its construction. It would be interesting to know if there are any less trivial constructions, that is, does there exist a loop-free matroid $M$ such that there is a weak map from $M$ onto its dual.

$\endgroup$
  • $\begingroup$ Thank you for your thoughts and ideas! $\endgroup$ – Moritz Nov 12 '16 at 13:35

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.