Non-emptiness (Matroid)

discrete-mathematics combinatorics

Definition

Non-emptiness (Matroid)

The non-emptiness axiom for a matroid $M=(E,\mathcal{I})$ states that

$$\varnothing \in \mathcal{I}.$$

Equivalently, at least one subset of the ground set, namely the empty set, is an independent set.

Interpretation

This is the weakest of the three matroid axioms. It guarantees that the independence family is non-empty and contains the smallest possible subset.

In the standard examples this is immediate:

• the empty set of vectors is linearly independent;
• the empty edge set is acyclic;
• the empty set has size at most $k$ in any uniform matroid.

Without non-emptiness, the heredity and exchange axioms would have nothing to act on.