A matroid is an independence system in which a smaller admissible selection can always grow using an element of a larger admissible selection. This exchange rule abstracts linear independence of vectors and the selection of edges forming a forest. It forces all matroid bases to have the same cardinality and makes the matroid greedy algorithm correct for maximizing their total weight. The useful surprise is that local choices become globally optimal because of a structural rule about admissible subsets, rather than a special numerical coincidence.
The weighted three-vector matroid below lets us inspect every subset and every possible size comparison. Its three vectors give three two-element matroid bases, yet their total weights differ. The graphic matroid of a graph triangle has exactly the same admissible labels. A pregeometry is a finitary closure-theoretic extension to possibly infinite sets.
A **matroid** is a combinatorial structure that generalizes the notion of linear independence in vector spaces to more abstract settings. It is defined by a pair \((S, I)\), where: - \(S\) is a finite set of elements. - \(I\) is a collection of subsets of \(S\) (called independent sets) that satisfy certain properties.
New to topics? Read the docs here!