Free matroid

In mathematics, the free matroid over a given ground-set is the matroid in which the independent sets are all subsets of . It is a special case of a uniform matroid; specifically, when has cardinality , it is the uniform matroid . The unique basis of this matroid is the ground-set itself, . Among matroids on , the free matroid on has the most independent sets, the highest rank, and the fewest circuits.

Every free matroid with a ground set of size is the graphic matroid of an -edge forest.

Free extension of a matroid

The free extension of a matroid by some element , denoted , is a matroid whose elements are the elements of plus the new element , and:

• Its circuits are the circuits of plus the sets for all bases of .
• Equivalently, its independent sets are the independent sets of plus the sets for all independent sets that are not bases.
• Equivalently, its bases are the bases of plus the sets for all independent sets of size .

References