Exchangeability (Matroid)

discrete-mathematics combinatorics

Definition

Exchangeability (Matroid)

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

$$X,Y\in \mathcal{I},|X|<|Y|⟹\exists e\in Y\setminus X:X\cup \{e\}\in \mathcal{I}.$$

A smaller independent set can always be extended by some element of a larger independent set while staying independent.

Interpretation

Exchangeability is the axiom that gives matroids their distinctive strength. While non-emptiness and heredity only describe a downward-closed family, exchangeability forces independent sets to grow in a balanced way.

In the standard examples:

• for the vector matroid, if $|X|<|Y|$ with both linearly independent, then $\mathrm{span}(X)$ has smaller dimension than $\mathrm{span}(Y)$, so some $e\in Y$ lies outside $\mathrm{span}(X)$, and $X\cup \{e\}$ is independent;
• for the graphic matroid, if $|X|<|Y|$ with both forests, some edge of $Y$ connects two components of the forest $X$ without creating a cycle;
• for the uniform matroid $U_{k,n}$, any $e\in Y\setminus X$ works, since $X\cup \{e\}$ still has size at most $k$.

Consequence: all bases have the same size

Equal-cardinality bases

In a matroid, every basis has the same cardinality.

Proof

Suppose $X,Y$ are bases with $|X|<|Y|$. By exchangeability, some $e\in Y\setminus X$ makes $X\cup \{e\}$ independent. But $X$ was a maximal independent set, so $X\cup \{e\}$ cannot be independent. Contradiction. Hence $|X|=|Y|$.

This common cardinality is the rank of the matroid.

Why greedy works

Exchangeability is the axiom that makes the greedy algorithm optimal. Whenever the greedy procedure stops with a non-maximal independent set, exchangeability guarantees that some still-available element can extend it, so greedy can only stop at a basis. The balancing effect of exchange is what prevents greedy from being trapped by a bad early choice.