matroid
Sign in to saveIn combinatorics, 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 terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice.
Wikidata facts
- Image
- Vamos matroid.svg
Show 1 more fact
- Stack Exchange tag
- math.stackexchange.com/tags/matroids
Sources (3)
via Wikidata · CC0
~36 min read
Article
32 sectionsContents
- Independent sets <span class="anchor" id="independent_sets_anchor"></span>
- Bases and circuits <span class="anchor" id="bases_circuits_anchor"></span>
- Rank functions <span class="anchor" id="rank_func_anchor"></span>
- Closure operators <span class="anchor" id="closure_ops_anchor"></span>
- Flats<span class="anchor" id="closed_sets_flats_anchor"></span>
- Hyperplanes (coatoms)
- Graphoids
- Examples
- Free matroid
- Uniform matroids
- Matroids from linear algebra
- Matroids from graph theory
- Matroids from field extensions
- Basic constructions
- Duality
- Minors
- Sums and unions
- Algorithms
- Matroid software
- Polynomial invariants
- Characteristic polynomial
- Beta invariant
- Whitney numbers
- Tutte polynomial
- Infinite matroids
- History
- Researchers
- Footnotes
- See also
- Citations
- References
- External links
In combinatorics, 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 terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice.
Matroid theory borrows extensively from the terms used in both linear algebra and graph theory, largely because it is the abstraction of various notions of central importance in these fields. Matroids have found applications in geometry, topology, combinatorial optimization, network theory, and coding theory.