Heredity (Matroid)

discrete-mathematics combinatorics

Definition

Heredity (Matroid)

The heredity axiom (also called the monotonicity property) for a matroid $M=(E,\mathcal{I})$ states that

$$X\subseteq Y,Y\in \mathcal{I}⟹X\in \mathcal{I}.$$

Every subset of an independent set is independent.

Interpretation

Heredity says independence is downward closed. If a collection of objects is independent, then any subcollection is also independent.

In the standard examples this matches intuition:

• a subset of a linearly independent set of vectors is linearly independent;
• a subgraph of a forest is a forest;
• a subset of a set of size at most $k$ still has size at most $k$.

Combined with non-emptiness, heredity ensures that the independence family is a downward-closed collection containing the empty set, but it does not yet force the rich structure that makes greedy algorithms work. That role belongs to exchangeability.