2

Let $r_1,r_2\colon 2^E\to \mathbb Z_{\geq0}$ be two rank functions of matroids $(E,\mathcal F_1)$ and $(E,\mathcal F_2)$ respectively. Is $$r\colon 2^E\to \mathbb Z_{\geq0}:X\mapsto \max\{r_1(X),r_2(X)\}$$ the rank function of a matroid?

Notice that $r$ is the rank function of a matroid if and only if for all $X,Y\subseteq E$ it holds that:

(R1) $|r(X)|\leq |X|$,

(R2) if $X\subseteq Y$, then $r(X)\leq r(Y)$,

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

It is easy to show that $r$ satisfies (R1) and (R2). However, I am unable to prove or disprove (R3). Does anyone have an idea? Thanks in advance.

Math
  • 824

1 Answers1

2

A key fact about the rank function $r$ of a matroid is that the inclusion-maximal sets in $\{F : r(F) = \#F\}$ all have the same cardinality. We use this fact to provide counterexample to the claim that the max of two matroid rank functions is a matroid rank function.

Let $E = \{1,2,3\}$ and $M_1, M_2$ be the matroids on $E$ with bases $B_1=\{\{1,2\}\}$ and $B_2 = \{\{2\},\{3\}\}$, respectively. Let $r : 2^{E} \to \mathbb{Z}$ take a subset $F \subseteq E$ to the maximum of the ranks as defined in the original post. Then the inclusion-maximal subsets $F$ of $E$ satisfying $r(F) = \#F$ are $\{1,2\}$ and $\{3\}$. So $r$ can't be the rank function a matroid because these sets have different sizes.

Aaron Dall
  • 1,182