From Wikipedia, the free encyclopedia
- Basic concepts
- Matroid – Abstraction of linear independence of vectors
- Dual matroid – Matroid with complemented basis sets
- Matroid rank – Maximum size of an independent set of the matroid
- Examples
- Fano plane – Geometry with 7 points and 7 lines
- Uniform matroid – Matroid in which every permutation is a symmetry
- Vámos matroid – Matroid with no linear representation
- MacLane matroid – Geometric structure of 8 points and 8 lines
- Matroids from linear algebra
- Matroid representation – Vectors with given pattern of independence
- Linear independence – Vectors whose linear combinations are nonzero
- Basis (linear algebra) – Set of vectors used to define coordinates
- Rank (linear algebra) – Dimension of the column space of a matrix
- Steinitz exchange lemma – Extension of independent vectors to bases
- Binary matroid – Abstraction of mod-2 vector independence
- Regular matroid – Matroid that can be represented over all fields
- Spark (mathematics) – Fewest dependent columns in a matrix
- Matroids from abstract algebra
- Algebraic matroid – Abstraction of algebraic independence
- Algebraic independence – Set without nontrivial polynomial equalities
- Transcendence degree – Field extension that is not algebraicPages displaying short descriptions of redirect targets
- Dowling geometry – Matroid associated with a group
- Matroids from graphs
- Graphic matroid – Matroid with graph forests as independent sets
- Spanning tree – Tree which includes all vertices of a graph
- Circuit rank – Fewest graph edges whose removal breaks all cycles
- Cycle space – All even-degree subgraphs of a graph
- Cycle basis – Cycles in a graph that generate all cycles
- Bicircular matroid – Abstraction of unicyclic subgraphs
- Gammoid – Abstraction of disjoint paths in directed graphs
- Biased graph – Graph with a list of distinguished cycles
- Gain graph – Graph with group-labeled edges
- Signed graph – Graph with sign-labeled edges
- Additional constructions of matroids
- Partition matroid – Direct sum of uniform matroids
- Paving matroid – Matroid without short circuits
- Rigidity matroid – Abstraction of bar-and-joint frameworks
- Structures equivalent to matroids
- Cryptomorphism – Non-obvious mathematical equivalance
- Geometric lattice – Join-meet algebra on matroid flats
- Pregeometry (model theory) – Formulation of matroids using closure operators
- Oriented matroids
- Oriented matroid – Abstraction of ordered linear algebra
- CC system – Ternary relation on points in the plane
- Mnëv's universality theorem – Realization of semialgebraic sets by points
- Separoid – Relation on disjoint pairs of sets
- Algorithmic problems on matroids
- Greedy algorithm – Sequence of locally optimal choices
- Weighted matroid – Objective function for greedy algorithms
- Minimum spanning tree – Least-weight tree connecting graph vertices
- Matroid intersection – Shared independent set of two matroids
- Matroid partitioning – Subdivision into few independent sets
- Matroid parity problem – Largest independent set of paired elements
- Matroid oracle – Subroutine for testing independence
- Criss-cross algorithm – Method for mathematical optimization
- Matroid generalizations of graph theory
- Matroid girth – Abstraction of graph shortest cycles
- Bipartite matroid – Abstraction of 2-colorable graphs
- Eulerian matroid – Independence system partitionable into circuits
- Ear decomposition – Partition of graph into sequence of paths
- Branch-decomposition – Hierarchical clustering of graph edges
- Clique-sum – Gluing graphs at complete subgraphs
- Matroid minor – Matroid obtained by restrictions and contractions
- Rota's conjecture – Conjecture on forbidden minors of matroids
- Tutte homotopy theorem – On composition of paths in matroids
- Whitney's planarity criterion – Characterization of planar graphs by matroids
- Matroid generalizations of discrete geometry
- Sylvester matroid – Abstract geometry without 2-point lines
- Sylvester–Gallai theorem – Existence of a line through two points
- Rota's basis conjecture – On rearrangement of bases in matroids
- K-set (geometry) – Points separated from others by a line
- Arrangement of hyperplanes – Partition of space by a hyperplanes
- Matroid polynomials
- Tutte polynomial – Algebraic encoding of graph connectivity
- Colored matroid – Abstract structure with colored elements
- Ingleton's inequality – Property of rank functions of matroids
- Related structures
- Greedoid – Set system used in greedy optimization
- Antimatroid – Mathematical system of orderings or sets
- Coxeter matroid – Group-theoretic generalization of matroids
- Matroid embedding – Set system related to matroids
- Matroid polytope – Convex hull of indicator vectors of bases
- Polymatroid – Multiset analogue of matroids
- Submodular set function – Set-to-real map with diminishing returns
