Properties of the rank function on independence systems

70 Views Asked by At

Let $\mathcal{M}=(X,\mathcal{I})$ a matroid on $X$ (here $\mathcal{I}$ is the collection of independent subsets of $\mathcal{M}$). If $\rho$ denotes the corresponding rank function, namely the function $$ \rho(A)=\max \{|B|: B \in \mathcal{I} \cap \mathfrak{P}(A)\} $$ (here $\mathfrak{P}(A)$ stands for the powerset of $A$), we may define the set operator $$ \sigma_\rho(A)=\{x \in X: \, \rho(A)=\rho(A \cup \{x\})\}, $$ which turns out to be a closure operator. We will say that $x$ depends on $A$ if $\rho(A)=\rho(A \cup \{x\})$. In order to prove that $\sigma$ is increasing, it suffices to see that if $x$ depends on $A$ and $A \subseteq B$, then $x$ depends on $B$.

Well, my question is: if $\mathcal{I}$ is only an independence system (a nonempty collection of subsets which is closed under taking subsets), is $\sigma_\rho$ increasing? Can you help me, please?

P.S. Probably $\sigma_\rho$ is not idempotent and, hence, in general, it is not a closure operator. But it should be a pre-closure operator.

1

There are 1 best solutions below

0
On BEST ANSWER

Let's take the simplest counterexample to the exchange property. We want independent sets $A$ and $B$ such that $|A|>|B|$, but there is no $x\in A\setminus B$ such that $B\cup \{x\}$ is independent. So let $X = \{1,2,3\}$, $A = \{1,2\}$ and $B = \{3\}$, and $\mathcal{I} = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}\}$.

This gives an example where $\sigma_\rho$ is not increasing. Let $C = \{3\}$ and $C' = \{1,3\}$. We have $\rho(C) = \rho(C\cup \{1\}) = \rho(C\cup \{2\}) = 1$, so $\sigma_\rho(C) = \{1,2,3\}$. But $\rho(C') = 1$, while $\rho(C'\cup \{2\}) = 2$, so $\sigma_\rho(C') = C' = \{1,3\}$. Thus $\sigma_\rho$ is not increasing.