The relation between the closure and the contraction of a matroid M.

104 Views Asked by At

Here is the relation I am trying to justify:

$cl_{ M/T}(X) = cl_M(X \cup T) - T$ for all $X \subseteq E - T.$

Why this relation true?

Any proof will be greatly appreciated!

**Here are all what I know about contraction and the closure operator: **

The contraction of $T$ from $M$ is given by $$M/T = (M^* \setminus T)^*$$ where the backward slash means deletion.

I know the following relations between contraction and the closure operator and deletion and the closure operator:

For all $X \subseteq E - T,$ we have

$$cl_{M\setminus T}(X) = cl_{M}(X) - T.$$

$$cl_{M/T}(X) = cl_{M}(X \cup T) - T.$$

I also know some identities about contraction and deletions, but I am not sure if they are useful here, I also know the spanning sets of deletion and contration of a matroid and the condition on the rank function of this matroid $M$ and $T$ that makes contraction same as deletion. But I do not know how to combine these ideas to prove the above identity. Any help will be greatly appreciated!

1

There are 1 best solutions below

2
On BEST ANSWER

So, recall that the independents of $M/T$ are sets $A\subseteq E\setminus T$ such that $A\cup R$ is independent on $M$ and $R$ is a maximal independent subset of $T$. This implies that $r_{M/T}(X)=r_M(X\cup T)-r_M(T)$ (or you can use duality and that the rank of deleting is just restricting the rank of the matroid). Now, to show the equality, we can take $x \in cl_{M/T}(X)$ and so $r_{M/T}(X\cup x)=r_{M/T}(X)$ which implies that $r_M(X\cup T\cup x)=r_M(X\cup T)$ and so $x\in cl_M(X\cup T)$. Furthermore, as $x \in E\setminus T$ then $x\not \in T$ so $x\in cl_M(X\cup T)\setminus T$. All of these implications are reversible.