Explicitly describe the cryptomorphism between greedoids and greedy set operators

76 Views Asked by At

A greedoid $\mathcal{F}$ on a finite ground set $E$ is cryptomorphic to an operator $\sigma$ (usually - and improperly - called the closure operator of the greedoid) such that:

  1. $X \subseteq \sigma(X)$;

  2. $X\subseteq Y \subseteq \sigma(X) \implies \sigma(X)=\sigma(Y)$;

  3. suppose that $x \notin X$ and $z \notin \sigma(X \cup \{x\}) \setminus \{z\})$ for all $z \in X \cup x$. Then $x \in \sigma(X \cup \{y\}) \implies y \in \sigma(X \cup \{x\})$.

My intention is to explicit describe the cryptomorphism by means of a bijection between the set system of the feasible sets of the greedoid and the "closure" operator.

To this end, as $X$ is feasible if and only if $x \notin \sigma(X \setminus \{x\})$ for each $x \in X$ (here $\sigma$ denotes the closure operator of the greedoid), I expect that $\mathcal{F}_\sigma:=\{X: \, x \notin \sigma(X \setminus \{x\}) \,\, \forall x \in X \}$ whenever $\sigma$ is a set operator satisfying the properties 1-3 listed above.

Now, I want to construct its inverse, namely a map which associates with the feasible sets of a matroid a set operator satisfying the properties 1-3 listed above. Reasoning by analogy with the case of matroids (whose resulting map is $\mathcal{F} \to \Phi_\mathcal{F}$, where

$$ \Phi_\mathcal{F}(X):=\{z \in E \mid \, \exists Y \subseteq X \,\, s.t. Y \in \mathcal{F} \,\, and \,\, Y \cup \{z\} \notin \mathcal{F}\} $$ for each $X \subseteq E$),

I surmise that if $\mathcal{F}$ is a matroid, then

$$ \phi_\mathcal{F}(X):=X \cup \left\{\begin{array}{llll} \{z \in E \setminus X: \, X\cup \{z\} \notin \mathcal{F}\} & {\rm if \,\,} X \in \mathcal{F} \\ \bigcup\limits_{Y \subseteq X,\,\, Y \in \mathcal{F}} \phi_\mathcal{F}(Y)& {\rm otherwise} \\ \end{array} \right. $$

is the closure operator of $\mathcal{F}$ and it is the inverse map of the correspondence exhibited above.

However, I do not manage to show my claim. Is it correct?