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
Canonical name	MatroidIndependenceAxioms
Date of creation	2013-03-22 14:44:05
Last modified on	2013-03-22 14:44:05
Owner	sgraves (6614)
Last modified by	sgraves (6614)
Numerical id	6
Author	sgraves (6614)
Entry type	Proof
Classification	msc 05B35
Synonym	matroid independent sets