2

The question is pretty self explanatory. I'm working with the definitions:

Matroid (Bases) $(E,\mathcal{B})$

1) No base is a subset of another base

2) $B_1,B_2 \in \mathcal{B}$ and $e \in B_1$ implies $\exists f \in B_2$ st $B_1 - e + f \in \mathcal{B}$.

Matroid (circuits) $(E,\mathcal{C})$

1) $\varnothing \notin \mathcal{C}$

2) No circuit proper subset of another circuit

3) $e \in C_1 \cap C_2$, $C_1 \neq C_2$ implies $\exists C_3 \in \mathcal{C}$ st $C_3 \subseteq C_1 \cup C_2 - e$.

My idea was to try to prove that if we do have a set of circuits, we can construct a set of bases and vice versa. At this point I tried a couple of things, but to be honest am trying to do this without any proper intuition of what these sets are, and have no idea what a good approach would be. Any ideas?

walkar
  • 3,844
BallzofFury
  • 1,154

2 Answers2

3

The problem is impossible without some additional information ensuring that $\langle E,\mathscr{B}\rangle$ and $\langle E,\mathscr{C}\rangle$ are the same matroid, presented once in terms of bases and once in terms of circuits, and not two different matroids on the same underlying set $E$. In other words, you have to know the relationship between $\mathscr{B}$ and $\mathscr{C}$.

If you know the notion of independent set in a matroid, this is straightforward: bases are maximal independent sets, circuits are minimal dependent sets, and $I\subseteq E$ is independent iff $I\subseteq B$ for some $B\in\mathscr{B}$ iff $\forall C\in\mathscr{C}(C\nsubseteq I)$. Starting here, it’s fairly straightforward to prove the desired result.

You may already have access to something better, but the discussion of matroids in Wikipedia isn’t actually too bad. You might look especially at the Definition section and, for some simple examples, the Uniform matroids and the Matroids from linear algebra sections.

Brian M. Scott
  • 616,228
  • Thanks a lot, I feel there's a little more grounding to the problem now. For clarification, what do you mean with the notation $\mathscr{C}(C\subsetneq I)$? – BallzofFury Feb 18 '15 at 11:21
  • @BallzofFury: You're welcome. As for the expression, you're missing part of it: it's $\forall C\in\mathscr{C}(C\nsubseteq I)$. In words, for each circuit $C$, $C$ is not a subset of $I$. That is, a set is independent if and only if it does not contain a circuit. – Brian M. Scott Feb 18 '15 at 11:27
1

Ah I see. So if $\mathscr{B} = \{E\}$, all $I \subseteq E$ are independent, so $C = \varnothing$. If it wasn't there would exist a subset of $E$ which isn't included in any subset of $E$ (all subsets are independent), so clearly false.

On the other hand if $\mathscr{C} = \varnothing$, $I \subseteq E$ is independent if for all $C \in \mathscr{C}$ we have $C \nsubseteq I$. This is vacuously true for all subsets, so the independent sets are all subsets of $E$. Therefore the only possible base (satisfying the subset property of a base) is the entire set $E$.

Does that sound about right?

BallzofFury
  • 1,154