USER:DAVID EPPSTEIN MATROID THEORY

Matroid Theory

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 algebraic; 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