Jump to content

User:David Eppstein/Matroid Theory

From Wikipedia, the free encyclopedia
Matroid Theory

Matroid Theory

[edit]
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