In mathematics, the free matroid over a given ground-set ''E'' is the

matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

in which the independent sets are all subsets of ''E''. It is a special case of a uniform matroid. The unique

basis Basis may refer to: Finance and accounting *Adjusted basis, the net cost of an asset after adjusting for various tax-related items *Basis point, 0.01%, often used in the context of interest rates * Basis trading, a trading strategy consisting o ...

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

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 \

for all bases

B

M

. * Equivalently, its independent sets are the independent sets of

M

plus the sets

I\cup \

for all independent sets

I

that are ''not'' bases. * Equivalently, its bases are the bases of

M

plus the sets

I\cup \

for all independent sets of size

\text(M)-1

References

Matroid theory {{combin-stub