Search code examples
algorithmsetproofcardinality

All maximal independent sets of a matroid have the same cardinality

How to prove that all maximal independent sets of a matroid have the same cardinality.

Provided a matroid is a 2-tuple (M,J ) where M is a finite set and J is a family of some of the subsets of M satisfying the following properties:

  1. If A is subset of B and B belongs to J , then A belongs to J ,
  2. If A, B belongs to J , |A| <= |B|, and x belongs to A - B, then there exists y belongs to B - A such that (B U {x})- {y} belongs to J.

The members of J are called independent sets.

Solution

  • Assume to the contrary that |A| < |B|, and A is not maximally independent.

    Consider the following Venn diagram

    enter image description here

    Clearly B \ A (the only-blue part) is nonempty, as the cardinality of B is larger than that of A. Also, clearly A \ B (the only-orange part) is nonempty, as otherwise A ⊂ B, and, by definition, A is not maximally independent.

    Hence, by the exchange property, there is some x ∈ A \ B, y ∈ B \ A, such that B ∪ {x} \ {y} ∈ J as well. Let's call this set C. Note that if we would draw the Venn diagram for A and C (now the blue circle is C):

    1. |B| = |C| (the blue circle has the same size)

    2. |(A \ {x}) \ C| < |A \ B| (the only-orange part is smaller than before)

    Now we can repeat the argument about A and C, and so on. Note, however, that we can't repeat it indefinitely, as A is assumed to be finite. Hence, at some point we will reach the contradiction that the orange set is completely contained in the blue set, which we already saw before is impossible (that would mean, by definition, that it is not maximally independent).