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