Combinatorial structure

A combinatorial structure whose elements carry distinct labels from a prescribed finite set. For example, a rooted tree can have labelled vertices; assigning labels is part of the structure counted by an exponential generating function.

An independence system consists of a finite set $E$ and a nonempty family $\mathcal{I}$ of subsets such that $I\in \mathcal{I}$ and $J\subseteq I$ imply $J\in \mathcal{I}$. This is the hereditary condition: deleting chosen elements keeps a selection admissible. In particular, the empty set belongs to $\mathcal{I}$. An independence system becomes a matroid when it also satisfies the matroid independence axioms for exchange. The hereditary nonmatroid greedy obstruction shows why deletion alone does not justify a greedy algorithm.

The ground set is the set of labelled elements available for selection. An independence system specifies which subsets of this ground set are admissible; in a linear matroid the labels index vectors, whereas in a graphic matroid they index edges.

On the ground set $E=\{x,y,z\}$, permit exactlyThis 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.