Jump to content

Free matroid

From Wikipedia, the free encyclopedia

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

[edit]

The free extension of a matroid by some element , denoted , is a matroid whose elements are the elements of plus the new element , and:

  • Its circuits are the circuits of plus the sets for all bases of .[2]
  • Equivalently, its independent sets are the independent sets of plus the sets for all independent sets that are not bases.
  • Equivalently, its bases are the bases of plus the sets for all independent sets of size .

References

[edit]
  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.