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 ${\displaystyle U{}_{4}^{4}}$). More generally, the graphic matroid of a forest with n edges is ${\displaystyle U{}_{n}^{n}}$.

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.

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}$.

References

1. Oxley, James G. (2006). Matroid Theory. Oxford Graduate Texts in Mathematics. Vol. 3. Oxford University Press. p. 17. ISBN   9780199202508.
2. Welsh, D. J. A. (2010). Matroid Theory. Courier Dover Publications. p. 30. ISBN   9780486474397.
3. Bonin, Joseph E.; de Mier, Anna (2008). "The lattice of cyclic flats of a matroid". Annals of Combinatorics. 12 (2): 155–170. arXiv: math/0505689 . doi:10.1007/s00026-008-0344-3.