Independence System

discrete-mathematics combinatorics

Definition

Independence System

An independence system is a pair $(E,\mathcal{I})$ where $E$ is a finite non-empty set and $\mathcal{I}\subseteq 2^E$ is a family of independent sets satisfying two axioms:

1. Non-emptiness: $\varnothing \in \mathcal{I}$.
2. Heredity: If $X\subseteq Y$ and $Y\in \mathcal{I}$, then $X\in \mathcal{I}$.

Equivalently, $\mathcal{I}$ is a downward-closed family containing the empty set.

Interpretation

An independence system is the minimal structure that lets one speak of “acceptable” subsets with the property that subsetting never breaks acceptability. It captures the first two of the three matroid axioms.

The key point is that an independence system is weaker than a matroid. It drops exchangeability. As a result, two things that matroids guarantee can fail here:

• maximal independent sets may have different sizes;
• the greedy algorithm may return a suboptimal solution.

Why it is not yet a matroid

Without exchangeability, a small independent set can be stuck: no available element extends it, even though a larger independent set exists elsewhere. Greedy can then paint itself into a corner.

Concretely, take $E=\{a,b,c\}$ and

$$\mathcal{I}=\{\varnothing ,\{a\},\{b\},\{c\},\{a,b\}\}.$$

This is downward-closed and contains the empty set, so it is an independence system. But $\{a,b\}$ and $\{c\}$ are both maximal independent sets of different sizes, and the exchange axiom fails: $\{c\}$ cannot be extended by $a$ or $b$ to a size-$2$ independent set.

Relation to Matroids

A matroid is precisely an independence system that also satisfies exchangeability. In other words,

$$\text{matroid}=\text{independence system}+\text{exchange}.$$

This is why the matroid axioms are presented in two stages in many treatments: first the downward-closed shape, then the balancing axiom that turns the shape into something greedy can exploit.