Free matroid · Paulipedia

{\displaystyle U{}_{4}^{4}} — 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 $n$ edges is $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 $n$ , it is the uniform matroid $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 $M$ by some element $e\not \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$ .^[3]
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

Oxley, James G. (2006). Matroid Theory. Oxford Graduate Texts in Mathematics. Vol. 3. Oxford University Press. p. 17. ISBN 9780199202508.
Welsh, D. J. A. (2010). Matroid Theory. Courier Dover Publications. p. 30. ISBN 9780486474397.
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.