4
$\begingroup$

It is not hard to show that given a matroid ($E, L$) and a defined rank function, $L$ is exactly those subsets whose rank is equal to the size. The following question is about how to build up a matroid using a function that has exactly the same 3 properties as a rank function has.

Let $E$ be a finite set and $f$ a function from $\mathscr P(E)$ to $\mathbb{Z}$ such that:

  1. $f(\emptyset) = 0$

  2. Whenever $X \subseteq Y$, $f(X) \leq f(Y)$

  3. For any $X, Y$, $f(X)+f(Y) \geq f(X \cup Y)+f(X \cap Y)$

The question is: Show that the following set:

{$A \subseteq E \;|\; f(B) \geq |B| \hspace{.1cm} \forall \hspace{.1cm} B \subseteq A$} is the independent set of a matroid on $E$.

I mainly have difficulty in prove the exchange property. One of my attempts is to prove by contradiction. If I assume $X$ and $Y$ are both in $L$ and $|X| = |Y| + 1$, assume $Y \cup {x} \notin L$ for any $x \in X$. Then fix an $x \in X$ \ $Y$ and assume $Y_1 \subseteq Y$ satisfy $f(Y_1) < |Y_1|$. Say $Y_1 = A_1 \cup {x}$ where $A_1 \in L$. Then I can only conclude that:

$f(A_1) + f({x}) \geq |Y_1| > f(Y_1)$

I do not know how to proceed then.

$\endgroup$
  • $\begingroup$ What parts of the definition of a matroid using independent sets are you having difficulty proving? $\endgroup$ – Somos May 20 '19 at 4:07
  • $\begingroup$ I do not know how to prove the exchange property. One of my attempt is to use contradiction. If I assume$X$ and $Y$ are both in $L$ and $|X| = |Y| + 1$, assume $Y \cup {x} \notin L$ for any $x \in X$ \ $Y$. Then fix an $x \in X$ \ $Y$ and assume $Y_1 \subseteq Y$ satisfy $f(Y_1) < |Y_1|$. Say $Y_1 = A_1 \cup {x}$ where $A_1 \in L$ and then I can only conclude that $f(A_1) + f({x}) \geq |Y_1| > f(Y_1)$. Then I do not know how to proceed. $\endgroup$ – Sanae Kochiya May 20 '19 at 13:31
  • $\begingroup$ By the way, the second definition, the one saying whenever a set is in $L$, all of its subsets are also in $L$, has been proved by definition of $L$. $\endgroup$ – Sanae Kochiya May 20 '19 at 13:34
  • $\begingroup$ I strongly suggest that you place your comments in the body of your question in order that readers of your question know what is the source of your difficulty. Also, have you tried induction yet? $\endgroup$ – Somos May 20 '19 at 14:03
  • $\begingroup$ If I use induction, I guess I need to assume that for any proper subset $A$ of $E$, that given set in the question is the independent set of a matroid built on $A$. Could you provide a bit more details about how to go from $A$ to $E$? I assumed $|A| = |E| - 1$, $L$ is defined on $A$ as the question did. I then splitted $L$ into two parts: $L_1 =$ {$X \in L | f(X) = |X|$} and $L_2 =$ {$X \in L \ f(X) > |X|$}. Again I have trouble proving the exchange property in this case. $\endgroup$ – Sanae Kochiya May 20 '19 at 18:22
1
$\begingroup$

The question is a bit old, but maybe it still interests someone. The reason that it hasn't been answered so far is probably due to a problem with the given definition - it lacks something which forces $f(X)\leq |X|$, so in general, $f$ is not necessarily a rank function of a matroid, and can be the rank function of some polymatroid that is not a matroid.

But by adding this requirement ($f(X)\leq |X|$), then $f$ is the rank function of a matroid. It can be shown as follows (though probably some simpler proof exists).

First, I'd like to use my favorite definition of a matroid: $E$ is a finite set and $r:2^{E}\to \mathbb{N}$ is a function satisfying

I) $r(\emptyset)=0$,

II) $r(X)\leq r(X\cup \{x\})\leq r(X)+1$ for all $X\subset E, x\in E$,

III) For all $X\subset E, x,y\in E$, if $r(X)=r(X\cup \{x\})=r(X\cup \{y\})$ then $r(X)=r(X\cup \{x,y\})$.

$f$ in your definition (with additionally $r(X)\leq |X|$) satisfies this:

Clearly from (1) and (2) $f(X)\geq 0$. From (2) $f(X)\leq f(X\cup \{x\})$. From (3) we get $f(X\cup \{x\})+f(X \cap \{x\})\leq f(X)+f(\{x\})\leq f(X)+1$, the second inequality following from the additional property, so (assuming $x\notin X$, otherwise it is immediate) it follows that $f(X\cup \{x\})\leq f(X)+1$ and (II) holds.

To see that (III) holds we use (3) with $X\cup \{x\}$ and $X\cup \{y\}$, and assuming $x\neq y$, we get $f(X\cup\{x,y\})+f(X)\leq f(X\cup \{x\})+(X\cup \{y\})=2f(X)$, the equality following from the assumption in (III). So $f(X\cup \{x,y\})=f(X)$.

Now let $L'=\{A\subset E\ |\ r(A)=|A|\}$ (written slightly different than your $L$, but using $r(X)\leq |X|$ and $r(X\cup \{x\})\leq r(X)+1$ it's not hard to see that they are equal).

Consider $X,Y\in L'$ with $|Y|>|X|$. If $\forall y\in Y\setminus X, r(X\cup \{y\})=r(X)=|X|$, then using (III), $r(X\cup Y)=r(X)=|X|$, but it's easy to see from (II) that $r(Y)\leq r(X\cup Y)$, so $|Y|\leq |X|$, a contradiction. So $\exists y\in Y, r(X\cup \{y\})=r(X)+1=|X\cup \{y\}|$, so $X\cup \{y\}\in L$. This shows the exchange property. The hereditary property follows easily from (II).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.