How do the dependent sets of a matroid characterize the matroid?

Question

Wikipedia says:

The dependent sets of a matroid characterize the matroid completely. The collection of dependent sets has simple properties that may be taken as axioms for a matroid.

So I wonder what properties a collection of subsets need to satisfy so that it is the collection of dependent sets for a matroid? Thanks.

Answer 1

The Wikipedia entry that you cited gives the axioms that a collection of sets must satisfy in order to be the collection of independent sets of a matroid. In those axioms, replace "independent" by "not dependent" and you'll have axioms for the collection of dependent sets. The axioms will be rather ugly, since "dependent" is always preceded by "not", so you'll probably want to rewrite the axioms in logically equivalent ways. For example, instead of saying that, if $A\subseteq B$ and $B$ is not dependent, then $A$ is not dependent (the second of Wikipedia's axioms), you could equivalently say that, if $A\subseteq B$ and $A$ is dependent, then $B$ is dependent.

Answer 2

Let $E$ be a finite set and $\mathcal D \subseteq 2^E$. Consider the following (possible) properties of $\mathcal D$.

• (D1) $\emptyset \notin \mathcal D$
• (D2) If $D_1 \in \mathcal D$ and $D_2 \in 2^E$ with $D_1 \subseteq D_2$, then $D_2 \in \mathcal D$.
• (D3) $\forall D_1, D_2 \in \mathcal D: (D_1 \not= D_2) \supset ((D_1 \cap D_2 \in \mathcal D) \vee (\forall e \in E: (D_1 \cup D_2)\setminus \{e\} \in \mathcal D))$

Then, $\mathcal D$ is the set of dependent sets of a matroid on $E$ iff (D1), (D2) and (D3) hold for $\mathcal D$.

To see why consider first the axioms of circuits of a matroid $M$. Let $\mathcal C(M)$ be the set of circuits of $M$, and $\mathcal D(M)$ be the set of dependent sets of $M$, that is, $\mathcal C(M) \subseteq \mathcal D(M)$. Recall that a set is dependent in a matroid iff it contains a circuit as subset.

• (C1) $\emptyset \notin \mathcal C(M)$
• (C2) $\forall C_1, C_2 \in \mathcal C(M): (C_1 \subseteq C_2) \supset (C_1 = C_2)$
• (C3) If $C_1, C_2 \in \mathcal C(M)$ are distinct, then $\forall e \in C_1 \cap C_2\ \exists C_3 \in \mathcal C(M): C_3 \subseteq (C_1 \cup C_2)\setminus \{e\}$

Case 1 ($\supset$): Let $\mathcal D = \mathcal D(M)$ for a suitable matroid $M$ on $E$. Properties (D1) and (D2) are evident, that is, we have yet to show (D3). Let $D_1, D_2 \in \mathcal D(M)$.

Case 1.1 ($\exists C \in \mathcal C(M): C \subseteq D_1 \cap D_2$): Then, $D_1 \cap D_2 \in \mathcal D(M)$.

Case 1.2 ($\forall C \in \mathcal C(M): C \not\subseteq D_1 \cap D_2$): Then, $D_1 \cap D_2 \notin \mathcal D(M)$. Let $x \in E$. Choose $C_1, C_2 \in \mathcal C(M)$ with $C_1 \subseteq D_1$ and $C_2 \subseteq D_2$.

Case 1.2.1 ($x \in C_1 \wedge x \in C_2$): Then, $x \in C_1 \cap C_2$ and so $\exists C \in \mathcal C(M): C \subseteq (C_1 \cup C_2)\setminus \{x\} \subseteq (D_1 \cup D_2)\setminus \{x\}$ via (C3), that is, $(D_1 \cup D_2)\setminus \{x\} \in \mathcal D(M)$.

Case 1.2.2 ($x \in C_1 \wedge x \notin C_2$): Then, $C_2 \subseteq (D_1 \cup D_2)\setminus \{x\}$.

Case 1.2.3 ($x \notin C_1 \wedge x \in C_2$): Then, $C_1 \subseteq (D_1 \cup D_2)\setminus \{x\}$.

Case 1.2.4 ($x \notin C_1 \wedge x \notin C_2$): Then, $C_1 \subseteq (D_1 \cup D_2)\setminus \{x\}$.

Case 2 ($\subset$): Let $\mathcal D$ be a set for which (D1), (D2) and (D3) hold. Define $\mathcal C \subseteq \mathcal D$ as the minimal elements of $\mathcal D$ with respect to $\subseteq$. Then, (C1) and (C2) hold for $\mathcal C$ by its definition. Let $C_1, C_2 \in \mathcal C\subseteq \mathcal D$ be distinct with $x \in C_1 \cap C_2$. Since $\mathcal C$ is a clutter and $C_1 \not= C_2$, it follows that $\forall \ell \in \{1,2\}: C_1 \cap C_2 \subsetneq C_\ell$ and so $C_1 \cap C_2 \notin \mathcal D$ by definition of $\mathcal C$. Therefore, $(C_1 \cup C_2)\setminus \{x\} \in \mathcal D$ and so $\exists C \in \mathcal C \subseteq \mathcal D: C \subseteq (C_1 \cup C_2)\setminus \{x\}$, that is, (C3) holds.