proving that $r(X \cup cl(Y)) = r(cl(X) \cup cl(Y)).$

90 Views Asked by At

Here is the question I am trying to prove:

Let $M$ be a matroid, and $r$ and $cl$ be its rank function and its closure operator. Prove the following:

$(d)$ $r(X \cup Y) = r(X \cup cl(Y)) = r(cl(X) \cup cl(Y)) = r(cl(X \cup Y))$

Here is my attempt:

Second, proving that $r(X \cup cl(Y)) = r(cl(X) \cup cl(Y)).$

Since $X \subseteq cl(X)$ and $cl(Y) \subseteq cl(Y),$ then $X \cup cl(Y) \subseteq cl(X) \cup cl(Y) $ and hence by the properties of the rank function we have $r(X \cup cl(Y) \leq r(cl(X) \cup cl(Y)) $. Now, for proving the other direction I do not know how to get that $cl(X) \subseteq X.$ I know that $cl(Y) \subseteq cl(Y)$ and $r(X) = r(cl(X))$ but I do not know how to complete. Any help will be appreciated.

1

There are 1 best solutions below

3
On BEST ANSWER

Well, you don't need to show this because you know that $r(X \cup Y) \leq r(X \cup cl(Y)) \leq r(cl(X) \cup cl(Y)) \leq r(cl(X \cup Y))$ just by comparing sets and you also know that $r(Z)=r(cl(Z))$ where $Z = X\cup Y$, so you have equality in all of them.

Now, if you really want to show that $r(cl(X)\cup cl(Y))\leq r(X\cup cl(Y))$, start with a maximal independent in $X$, call it $B'\subseteq X$ such that $|B'|=r(X)$. Using that $X\subseteq X\cup cl(Y)\subseteq cl(X)\cup cl(Y)$, we can augment (Augmentation Theorem) $B'$ to a $B\subseteq X\cup cl(Y)$ maximal independent such that $|B|=r(X\cup cl(Y))$ and we can augment $B$ to a set $A\subseteq cl(X)\cup cl(Y)$ such that $|A|=r(cl(X)\cup cl(Y))$. Define $S ,T $ as the augmentation sets, that is, $B=B'\cup S$ and $A = B\cup T$, so that $A = B'\cup (T\cup S)$.

To get a contradiction, assume that $r(cl(X)\cup cl(Y)) = |A|>|B|=r(X\cup cl(Y))$, so $|T|>0$ and also $T\subseteq cl(X)\setminus X$. Now, just consider $B'\cup T\subseteq cl(X)$, this is independent because $A$ is independent and $|B'\cup T|>|B'|$, which implies that $r(cl(X))>r(X)$ which is not true, as you know.