Top Qs
Timeline
Chat
Perspective
Free matroid
From Wikipedia, the free encyclopedia
Remove ads
Remove ads
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; specifically, when E has cardinality , it is the 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.

Every free matroid with a ground set of size n is the graphic matroid of an n-edge forest.[2]
Remove ads
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle B} of .[3]
- 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 .
Remove ads
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads