Free matroid

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 $U{}_4^4$). More generally, the graphic matroid of a forest with Template:Mvar edges is $U{}_n^n$.

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

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

Free extension of a matroid

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

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

References

Template:Combin-stub