Show that $C^*(e,B)$ is the unique cocircuit that is disjoint from $B - e.$

Question

I want to prove the following question:

Let $B$ be a basis of a matroid $M.$ If $e \in B,$ denote $C_{M^*}(e, E(M) - B)$ by $C^*(e,B)$ and call it the fundamental cocircuit of $e$ with respect to $B.$\ $(a)$ Show that $C^*(e,B)$ is the unique cocircuit that is disjoint from $B - e.$\ $(b)$ If $f \in E(M) - B,$ prove that $f \in C^*(e,B)$ if and only if $e \in C (f,B).$

I knew the proof of the following question:

Prove that if $C$ is a circuit of a matroid $M$ and $e \in C,$ then $M$ has a basis $B$ such that $C = C(e, B).$

From here Constructing a basis for a matroid with a circuit in it.

Is not the proof of letter $(a)$ in my question is just the same as the question above but for dual matroids?

How about the proof of letter (b), should I use the strong elimination axiom for circuits or the weak elimination axiom or neither works?

Any ideas will be greatly appreciated.

Answer 1

Let $E=E(M)$, and let $\mathcal{B}$ denote the set of bases of $M$.

For part $(a)$, recall the following.

Let $B$ be a basis of a matroid $M$, and $e\in E-B$. Then $B+e$ contains a unique circuit, $C_M(e, B)$, which we call the fundamental circuit of $e$ with respect to $B$.

Now, $C_{M^*}(e, E-B)$ is the fundamental circuit of $e$ with respect to the basis $E-B$ in the dual matroid $M^*$. This circuit is contained in $E-B+e$, so is disjoint from $B-e$. It is also the unique such circuit, since it is a fundamental circuit. Since circuits in $M^*$ are cocircuits in $M$, we are done.

---

For part (b), we will first try to get a better understanding of what the fundemental cocricuit is.

Claim: Let $M$ is a matroid and $B\in\mathcal{B}$. If $e\in B$, then $$C^*(e, B) = E-\operatorname{cl}_M(B-e) = \{f\in E: (B-e+f) \in \mathcal{B}\}.$$

Proof. We show the first equality, then the second equality. $C^*(e, B)$ is a cocircuit contained in $E-B+e$. Now, $E-B+e$ contains $E-\operatorname{cl}_M(B-e)$ since $B-e\subseteq \operatorname{cl}_M(B-e)$. Since $B$ is an $M$-basis, $\operatorname{cl}_M(B-e)$ is a hyperplane in $M$. The complement of a hyperplane is a cocircuit, i.e., $E-\operatorname{cl}_M(B-e)$ is a cocircuit. We conclude $C^*(e, B) = E-\operatorname{cl}_M(B-e)$.

Now onto the second equality. We show $E-\operatorname{cl}_M(B-e)\subseteq \{f\in E: (B-e+f) \in \mathcal{B}\}$. Let $x\in E-\operatorname{cl}_M(B-e)$. Since $x\not\in \operatorname{cl}_M(B-e)$, $r(B-e+x) > r(B-e)$, so $B-e+x$ is a basis, since $B$ is a basis. Thus $x\in \{f\in E: (B-e+f) \in \mathcal{B}\}$. The other direction of the proof is analoguous. $\square $

By duality applied to our claim, we have that

$$C(f, B) = \{e\in E:(B-e+f)\in \mathcal{B}\},$$

since requiring $(E-B)-f+e$ to be a cobasis is the same as requiring $B-e+f$ to be a basis (not to be confused, note that $C^*(e, B)\subseteq E-B+e$ and $C(f, B)\subseteq B+f$). To conclude the argument, we use the claim and its dual version to observe that $f\in C^*(e, B)$ if and only if $B-e+f\in \mathcal{B}$ if and only if $e\in C(f, B)$, as desired.