Английская Википедия:Free matroid
Материал из Онлайн справочника
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>M</math> by some element <math>e\not\in M</math>, denoted <math>M+e</math>, is a matroid whose elements are the elements of <math>M</math> plus the new element <math>e</math>, and:
- Its circuits are the circuits of <math>M</math> plus the sets <math>B\cup \{e\}</math> for all bases <math>B</math> of <math>M</math>.[2]
- Equivalently, its independent sets are the independent sets of <math>M</math> plus the sets <math>I\cup \{e\}</math> for all independent sets <math>I</math> that are not bases.
- Equivalently, its bases are the bases of <math>M</math> plus the sets <math>I\cup \{e\}</math> for all independent sets of size <math>\text{rank}(M)-1</math>.
References
