If I have the matroid $M=(E,I)$ and $\mid X \mid + r(E\backslash X)-r(E) \geq 0 $ . Can someone give me any idea about how I can prove it ?I was thinking to: I know that $\mid X \mid \geq r(X)$ then I replace : $$r(X)+ r(E \backslash X)- r(E) \geq 0$$ $$r(X \cup (E \backslash X))+ r(X \cap (E \backslash X))- r(E) \geq 0$$ $$r(E) -r (E)\geq 0$$ and $ 0 \geq 0$ .\ I try to prove the inequality
Asked
Active
Viewed 59 times
0
-
What are we supposed to prove? – Mathematician 42 Apr 22 '16 at 20:11
-
@Elena: If $M$ is your matroid with rank function $r$, then $r'(X) := |X|+ r(E\setminus X) - r(E)$ is the rank function of the dual matroid of $M$. Follow the answer of Brian M. Scott below. – Moritz May 20 '16 at 20:55
1 Answers
1
One of the basic properties of the rank function is that
$$r(A\cup B)+r(A\cap B)\le r(A)+r(B)\tag{1}$$
for any $A,B\subseteq E$. Take $A=X$ and $B=E\setminus X$; then $A\cup B=E$ and $A\cap B=\varnothing$, so $(1)$ becomes
$$r(E)+r(\varnothing)\le r(X)+r(E\setminus X)\;.$$
Now use the fact that $r(A)\le|A|$ for all $A\subseteq E$ to deduce the desired inequality.
Brian M. Scott
- 616,228