In mathematics, the free matroid over a given ground-set E is the matroid in which the independent sets are all subsets of E.[1] It is a special case of a uniform matroid. 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 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]:1
  • 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

  1. "Definition:Free Matroid - ProofWiki". proofwiki.org. Retrieved 2020-11-07.
  2. Bonin, Joseph E.; de Mier, Anna (2007-02-12). "The Lattice of Cyclic Flats of a Matroid". arXiv:math/0505689.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.