Proving $r_{(k)}(X \cup Y) + r_{(k)}(X \cap Y) \leq r_{(k)}(X) + r_{(k)}(Y).$

Question

Here is the question I am trying to prove the inequality below of part $(a)$ in it:

$$r_{(k)}(X \cup Y) + r_{(k)}(X \cap Y) \leq r_{(k)}(X) + r_{(k)}(Y).$$

Let $M$ be a matroid on a set $E$ and $k$ be a non-negative integer not exceeding $r(M).$ Define $$r_{(k)}: 2^E \to \mathbb Z^+ \cup \{0\} \text{ by } r_{k}(X) = \operatorname{ min } \{k,r(X)\}.$$ $(a)$ Prove that $r_{(k)}$ is the rank function of a matroid on $E$ of rank $k.$

Here are my thoughts:

Recall Corollary $1.3.4,$ which states the properties required for a function to be the rank function of a matroid:

Let $E$ be a set. A function $r: 2^E \to \mathbb Z^+ \cup \{0\}$ is the rank function of a matroid on $E$ iff $r$ has the following properties:

\begin{enumerate}

\item $(R1)$ If $X \subseteq E,$ then $0 \leq r(X) \leq |X|.$

\item $(R2)$ If $X \subseteq Y \subseteq E,$ then $r(X) \leq r(Y).$

\item $(R3)$ If $X$ and $Y$ are subsets of $E,$ then $$r(X \cup Y) + r(X \cap Y) \leq r(X) + r(Y).$$

\end{enumerate}

Now, we will prove the previous statements for the new defined rank function $r_{(k)}.$

\textbf{Proof of $(R1)$:}

Let $X \subseteq E,$ by the given definition of the codomain of $r_{(k)}(X)$ in the question, we know that $0 \leq r_{(k)}(X).$ Now, since, by the properties of the rank function $r(X),$ we know that $r(X) \leq |X|$ and since the new rank function is defined as the minimum of $k$ (which is $\leq r(M)$ which is $\geq r(X)$ by $(R3)$) and $r(X),$ therefore $r_{(k)}(X)\leq |X|.$ Hence $$0 \leq r_{(k)}(X) \leq |X|$$ as required.

\textbf{Proof of $(R2)$:}

Assume that $X \subseteq Y \subseteq E,$ then $r(X) \leq r(Y)$ by $(R2)$ above and then $\operatorname{ min } \{k,r(X)\} \leq \operatorname{ min } \{k,r(Y)\}$ i.e., $r_{(k)}(X) \leq r_{(k)}(Y)$ as required.

\textbf{Proof of $(R3)$:}

Assume that $X$ and $Y$ are subsets of $E,$ we want to show that $$r_{(k)}(X \cup Y) + r_{(k)}(X \cap Y) \leq r_{(k)}(X) + r_{(k)}(Y).$$ Since $$r(X \cup Y) + r(X \cap Y) \leq r(X) + r(Y)$$ then since both sides are nonnegative integers so if we take the minimum of each term and $k$ we wil get the required.

Is my proof of $(R3)$ for the new rank function correct or I need to use any ideas from below? could someone clarify this to me please?

$X\cap Y \leq X\cup Y$ and $X \leq X \cap Y$ and $Y \leq X \cap Y$

Answer 1

The result does not follow from the inequality

$$ r(X \cup Y) + r(X\cap Y) \leq r(X) + r(Y) $$ for arbitrary functions $r$. Indeed, $X, Y, X\cap Y, X\cup Y$ could be mapped to very different values given a proper function $f$ essentially having the following hold true $$ A + B \leq C + D \implies \min\{ k, A\} + \min_{}\{ k, B\} \leq \min_{}\{ k, C \} + \min_{}\{ k, D \} $$ for arbitrary $A, B,C,D$. However consider the case $$ (A, B , C, D) = (k+6, k+12, 2k, 18),\quad k > 18, $$ we have

$$ A + B \leq C + D \iff 2k+18 \leq 2k+18 $$ but $$ \min\{ k, A\} + \min_{}\{ k, B\} = 2k > k + 18 = \min_{}\{ k, C \} + \min_{}\{ k, D \} \ . $$ (Having $A,B$ that will not be blocked by $\min$ but a big $C$ whose contribution will mostly be blocked by $\min$)

However let's prove the lemma darig proposed (from which the result follows, taking advantage of the properties of $r$).

Lemma: If have the real numbers $a,b,c,d,k$ with $$ c,d \leq a\quad (0) $$ and $$ a+b \leq c + d\quad (1) $$ then we have

$$ \min_{}\{a, k \} + \min_{}\{ b, k \} \leq \min_{}\{ c, k \} + \min_{}\{ d,k \}\ . $$ Proof:

For simplicity we will use the notation $X' = \min_{}\{ k, X \}$ (obviously $X' \leq k$ and $X' \leq X$). Therefore we only need to prove $a'+b'\leq c'+d'$. Also without loss of generality we assume $c\leq d$. We will exhaust all cases.

• if $d \leq k$ then $c\leq d \leq k \implies c'=c, d'=d$ so $a' + b' \leq a + b \overset{ (1) }{ \leq } c +d=c'+d'$.
• if $c \leq k < d \leq a$ then $$ a'+b' \leq k+b \overset{ (1) }{ \leq } k+c+\underbrace{ d-a }_{ \leq 0 } \leq k+c=c'+d'\ . $$
• if $k < c \leq d \leq a$ then $$ b' \leq k \iff k+b' \leq k + k\iff a' + b' \leq c' + d'\ . $$

We have exhausted all cases and are finished. $\blacksquare$

Unfortunately I don't think my proof gives too much insight to what is going on but I can't find one where I don't eventually run into cases.

Now in our problem we have

$$ r(X \cup Y) + r(X\cap Y) \leq r(X) + r(Y) $$

and need to prove

$$ \min_{}\{r(X \cup Y), k \} + \min_{}\{ r(X\cap Y), k \} \leq \min_{}\{ r(X), k \} + \min_{}\{ r(Y),k \}\ . $$ Let's name the following inequalities (which hold from the matroid rank properties) $$ r(X),r(Y)\leq r(X \cup Y) \quad (0) $$ $$ r(X \cup Y) + r(X\cap Y) \leq r(X) + r(Y) \quad (1) $$

We see that the problem boils down to a simple application our lemma.