matroid

A matroid is a combinatorial abstraction of linear independence. Formally, a matroid M consists of a finite set E and a collection I of subsets of E, called the independent sets, satisfying three axioms: the empty set is independent; every subset of an independent set is independent (hereditary property); and if A and B are independent with |A| < |B|, then there exists an element in B \ A that can be added to A to create a larger independent set (the augmentation axiom). The maximal independent sets are called bases; minimal dependent sets are circuits.

Associated with a matroid is the rank function r: P(E) → N, where r(X) is the size of a largest independent subset of X. The closure of a set X is cl(X) = {e in E : r(X ∪ {e}) = r(X)}. A basis has size r(E). The dual matroid M* has bases that are complements of bases of M. Minors are obtained by deleting elements or by contracting elements.

Matroids generalize several familiar structures. Graphic matroids arise from graphs: E is the edge set and independent sets are acyclic edge subsets. Vector matroids arise from a finite set of vectors in a vector space over a field, where independence is linear independence. A matroid is representable (or realizable) over a field if it arises in this way.

Matroid theory underpins many optimization algorithms. The greedy algorithm correctly finds a maximum-weight independent set in every matroid, making matroids a natural framework for problems that admit greedy solutions. They also appear in algorithmic applications, geometry, and coding theory.