# matroid independence axioms

Hassler Whitney’s definition of a matroid was based upon the idea of independent sets and was given in terms of the following three axioms:

A finite set $E$ along with a collection $\mathcal{I}$ of subsets of $E$ is a matroid if $M=(E,\mathcal{I})$ meets the following criteria:
(I1) $\emptyset\in\mathcal{I}$;
(I2) If $I_{1}\in\mathcal{I}$ and $I_{2}\subseteq I_{1}$, then $I_{2}\in\mathcal{I}$;
(I3) If $I_{1},I_{2}\in\mathcal{I}$ with $|I_{1}|<|I_{2}|$, then there is some $e\in I_{2}$ such that $I_{1}\cup\{e\}\in\mathcal{I}$.

The third axiom, (I3), is equivalent to the following alternative axiom:

(I3*) If $S,T\in\mathcal{I}$ and $S,T\subset U\subset E$ and $S$ and $T$ are both maximal subsets of $U$ with the property that they are in $\mathcal{I}$, then $|S|=|T|$.

###### Proof.

Suppose (I3) holds, and that $S$ and $T$ are maximal independent subsets of $A\subseteq E$. Also assume, without loss of generality, that $|S|<|T|$. Then there is some $e\in T$ such that $S\cup\{e\}\in\mathcal{I}$, but $S\subset S\cup\{e\}\subseteq A$, contradicting maximality of $S$.
Now suppose that (I3*) holds, and assume that $S,T\in\mathcal{I}$ with $|S|<|T|$. Let $A=S\cup T$. Then $S$ cannot be maximal in $A$ by (I3*), so there must be elements $e_{i}\in A$ such that $S\cup\{e_{i}\}\in\mathcal{I}$ is maximal, and by construction these $e_{i}\in T$. So (I3) holds. ∎

Title matroid independence axioms MatroidIndependenceAxioms 2013-03-22 14:44:05 2013-03-22 14:44:05 sgraves (6614) sgraves (6614) 6 sgraves (6614) Proof msc 05B35 matroid independent sets