Free matroid

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 ${\displaystyle n}$, it is the uniform matroid ${\displaystyle U{}_{n}^{n}}$.^[1] 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.

The graphic matroid of a forest with 4 edges, which is the free matroid with a ground set of size 4 (also the uniform matroid ${\displaystyle U{}_{4}^{4}}$). More generally, the graphic matroid of a forest with n edges is ${\displaystyle U{}_{n}^{n}}$.

Every free matroid with a ground set of size n is the graphic matroid of an n-edge forest.^[2]

Free extension of a matroid

The free extension of a matroid ${\displaystyle M}$ by some element ${\displaystyle e\not \in M}$, denoted ${\displaystyle M+e}$, is a matroid whose elements are the elements of ${\displaystyle M}$ plus the new element ${\displaystyle e}$, and:

• Its circuits are the circuits of ${\displaystyle M}$ plus the sets ${\displaystyle B\cup \{e\}}$ for all bases ${\displaystyle B}$ of ${\displaystyle M}$.^[3]
• Equivalently, its independent sets are the independent sets of ${\displaystyle M}$ plus the sets ${\displaystyle I\cup \{e\}}$ for all independent sets ${\displaystyle I}$ that are not bases.
• Equivalently, its bases are the bases of ${\displaystyle M}$ plus the sets ${\displaystyle I\cup \{e\}}$ for all independent sets of size ${\displaystyle {\text{rank}}(M)-1}$.