Misplaced Pages

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

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

This combinatorics-related article is a stub. You can help Misplaced Pages by expanding it.

• v
• t
• e

• Matroid theory
• Combinatorics stubs