5

Let $M$ be a matroid with $\mathcal C$ as set of circuits of $M$, and $\mathcal D$ as set of dependent sets of $M$, respectively.

Recall that $\mathcal C \subseteq \mathcal D$. We know that the strong elimination axiom holds for $\mathcal C$, that is,

$$\forall C_1, C_2 \in \mathcal C\ \forall x \in C_1 \cap C_2\ \forall y \in C_1\setminus C_2\ \exists C_3 \in \mathcal C: y \in C_3 \subseteq (C_1 \cup C_2)\setminus \{x\}.$$

Question: Does $\mathcal D$ also have this property, which is

$$\forall X, Y \in \mathcal D\ \forall x \in X \cap Y\ \forall y \in X\setminus Y\ \exists Z \in \mathcal D: y \in Z \subseteq (X \cup Y)\setminus \{x\}?$$

If it holds, what is a proof of this fact? If it does not, what is a counter-example?

Frenzy Li
  • 3,685
Moritz
  • 1,992

1 Answers1

5

The dependent sets do not necessarily satisfy the weak elimination axiom. For instance, if we have a matroid on $\{a,b,c\}$ with one circuit $\{a\}$, we have that $X=\{a,b\}$ and $Y=\{a\}$ are dependent sets, but there is no $Z$ that is a subset of $X\cup Y \setminus \{a\}$. Even if we ask that $X$ is not a subset of $Y$ and vice versa, a counterexample sets $X=\{a,b\}$ and $Y=\{a,c\}$, then eliminates $a$, but this fails because $\{b,c\}$ is independent.

The general issue is that not all dependent sets can be written as a union of circuits. If we have some $x\in X$ for a dependent set $X$ such that for all circuits $Y\subseteq X$ we have $x\not \in Y$, then, assuming weak elimination works, we can ask:

What is a minimal dependent set $X'$ such that $x\in X'$ and $X'\subseteq X$?

If such an $X'$ contains some circuit $Y$ with $y\in Y$, then we can use weak elimination on $y$ to get a dependent $Z\subseteq X'\setminus \{y\}$. Then $X''=Z\cup \{x\}$ is a dependent set with $x\in X''$ and $X''\subset X'$, so $X'$ was not minimal. Therefore, the minimal $X'$ contains no circuits. However, this is a contradiction, since $X'$ was defined to be dependent.

Side notes: If weak elimination held for dependent sets, it would imply strong elimination, since you could just union the element you were trying to preserve back onto the set if you had eliminated it. Also, if you want to find a dependent set which is not a union of circuits, one construction that will often work is to take a flat $F$ which is dependent and not the whole space. Then, for any $x\not\in F$ the set $F\cup\{x\}$ contains no circuits containing $x$. So, for instance, if this is the matroid of an arrangement of vectors, the vectors must be in general position (i.e. no subspace of less than full dimension contains more points than the subspace's dimension). Extending from this, you can, with a little effort, prove that weak elimination only works on dependent sets when every circuit has equally many elements (i.e. when the circuits are exactly the subsets of the base set of size $r+1$ where $r$ is the rank).

Milo Brandt
  • 60,888