In mathematics, the free matroid over a given ground-set E is the matroid in which the independent sets are all subsets of E. It is a special case of a uniform matroid; specifically, when E has cardinality n {\displaystyle n} , it is the uniform matroid U
n n {\displaystyle U{}_{n}^{n}} . The unique basis of this matroid is the ground-set itself, E. Among matroids on E, the free matroid on E has the most independent sets, the highest rank, and the fewest circuits. Every free matroid with a ground set of size n is the graphic matroid of an n-edge forest.
Free extension of a matroid The free extension of a matroid M {\displaystyle M} by some element e ∉ M {\displaystyle e\not \in M} , denoted M + e {\displaystyle M+e} , is a matroid whose elements are the elements of M {\displaystyle M} plus the new element e {\displaystyle e} , and:
Its circuits are the circuits of M {\displaystyle M} plus the sets B ∪ { e } {\displaystyle B\cup \{e\}} for all bases B {\displaystyle B} of M {\displaystyle M} . Equivalently, its independent sets are the independent sets of M {\displaystyle M} plus the sets I ∪ { e } {\displaystyle I\cup \{e\}} for all independent sets I {\displaystyle I} that are not bases. Equivalently, its bases are the bases of M {\displaystyle M} plus the sets I ∪ { e } {\displaystyle I\cup \{e\}} for all independent sets of size rank ( M ) − 1 {\displaystyle {\text{rank}}(M)-1} .
References