Maximal Independent Set (Matroid)

discrete-mathematics combinatorics

Definition

Maximal Independent Set (Matroid)

Let $M=(E,\mathcal{I})$ be a matroid. A independent set $B\in \mathcal{I}$ is maximal if no independent set properly contains it:

$$B\cup \{e\}\notin \mathcal{I}\text{for every }e\in E\setminus B.$$

Adding any remaining element of the ground set would make the set dependent. A maximal independent set is a basis of the matroid.

Interpretation

Maximality is an inclusion-wise notion, not a cardinality notion. A maximal independent set cannot be extended, but it need not be the largest independent set in any absolute sense. What makes maximality well-behaved in a matroid is exchangeability: it forces all maximal independent sets to have the same cardinality, so “maximal” and “maximum” coincide.

This is the property that distinguishes matroids from arbitrary independence systems. In a general downward-closed family, maximal independent sets can have different sizes. In a matroid they cannot.