matroid independence axioms

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

A finite setMathworldPlanetmath E along with a collectionMathworldPlanetmath of subsets of E is a matroid if M=(E,) meets the following criteria:
(I1) ;
(I2) If I1 and I2I1, then I2;
(I3) If I1,I2 with |I1|<|I2|, then there is some eI2 such that I1{e}.

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

(I3*) If S,T and S,TUE and S and T are both maximal subsets of U with the property that they are in , then |S|=|T|.


Suppose (I3) holds, and that S and T are maximal independent subsets of AE. Also assume, without loss of generality, that |S|<|T|. Then there is some eT such that S{e}, but SS{e}A, contradicting maximality of S.
Now suppose that (I3*) holds, and assume that S,T with |S|<|T|. Let A=ST. Then S cannot be maximal in A by (I3*), so there must be elements eiA such that S{ei} is maximal, and by construction these eiT. 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