= Hereditary nonmatroid greedy obstruction
On the <ground set> $E=\{x,y,z\}$, permit exactly
$$
\mathcal F=\{\varnothing,\{x\},\{y\},\{z\},\{y,z\}\},
\qquad w(x)=10,\quad w(y)=w(z)=6.
$$
This lists every admissible <subset>; the excluded <subsets> are $\{x,y\}$, $\{x,z\}$, and $\{x,y,z\}$. It is an <independence system>: deleting elements from $\{y,z\}$ produces its listed singletons or the <empty set>, and deleting from a singleton produces the <empty set>. But $I=\{x\}$ and $J=\{y,z\}$ violate exchange: neither $y$ nor $z$ can be added to $I$. Thus it is not a <matroid>.
The descending-weight <greedy algorithm> admits $x$ first, then rejects both $y$ and $z$, returning $\{x\}$ with weight $10$. Exchanging the tied order of $y,z$ changes nothing. The admissible pair $\{y,z\}$ weighs $12$, exceeding every singleton and the <empty set>, so it is the true optimum. Both $\{x\}$ and $\{y,z\}$ are <maximal elements> under inclusion of <subsets>, but only the pair has maximum <cardinality>. This identifies exactly where the <matroid greedy algorithm> loses its guarantee: heredity preserves admissibility under deletions, while exchange prevents a locally maximal selection from being too small.
Back to article page
