Free matroid
From HandWiki
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.[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.
Free extension of a matroid
The free extension of a matroid [math]\displaystyle{ M }[/math] by some element [math]\displaystyle{ e\not\in M }[/math], denoted [math]\displaystyle{ M+e }[/math], is a matroid whose elements are the elements of [math]\displaystyle{ M }[/math] plus the new element [math]\displaystyle{ e }[/math], and:
- Its circuits are the circuits of [math]\displaystyle{ M }[/math] plus the sets [math]\displaystyle{ B\cup \{e\} }[/math] for all bases [math]\displaystyle{ B }[/math] of [math]\displaystyle{ M }[/math].[2]
- Equivalently, its independent sets are the independent sets of [math]\displaystyle{ M }[/math] plus the sets [math]\displaystyle{ I\cup \{e\} }[/math] for all independent sets [math]\displaystyle{ I }[/math] that are not bases.
- Equivalently, its bases are the bases of [math]\displaystyle{ M }[/math] plus the sets [math]\displaystyle{ I\cup \{e\} }[/math] for all independent sets of size [math]\displaystyle{ \text{rank}(M)-1 }[/math].
References
- ↑ Matroid Theory. Oxford Graduate Texts in Mathematics. 3. Oxford University Press. 2006. p. 17. ISBN 9780199202508.
- ↑ Bonin, Joseph E.; de Mier, Anna (2008). "The lattice of cyclic flats of a matroid". Annals of Combinatorics 12 (2): 155–170. doi:10.1007/s00026-008-0344-3.
 |  |
