View source for 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]].<ref>{{cite book
 | last = Oxley | first = James G. | authorlink = James Oxley
 | isbn = 9780199202508
 | page = 17
 | publisher = Oxford University Press
 | series = Oxford Graduate Texts in Mathematics
 | title = Matroid Theory
 | volume = 3
 | year = 2006}}</ref> The unique [[Basis of a matroid|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 [[Circuit of a matroid|circuits]] are the circuits of <math>M</math> plus the sets <math>B\cup \{e\}</math> for all [[Basis of a matroid|bases]] <math>B</math> of <math>M</math>.<ref>{{cite journal
 | last1 = Bonin | first1 = Joseph E.
 | last2 = de Mier | first2 = Anna
 | arxiv = math/0505689
 | doi = 10.1007/s00026-008-0344-3
 | issue = 2
 | journal = Annals of Combinatorics
 | pages = 155–170
 | title = The lattice of cyclic flats of a matroid
 | volume = 12
 | year = 2008}}</ref>
*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 [[Basis of a matroid|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 ==
{{Reflist}}

[[Category:Matroid theory]]


{{combin-stub}}