Matroids and greedy optimality

A finite matroid consists of a ground set E and a family of independent subsets. The empty set is independent, every subset of an independent set is independent, and augmentation holds: if independent A is smaller than independent B, some element of B outside A can be added to A while keeping independence. Heredity alone says deleting constraints is safe. Augmentation is the stronger property that prevents a smaller independent set from being completely stuck while a larger one exists.

A basis is an inclusion-maximal independent subset of the full ground set. Augmentation implies that all bases have the same size, called the rank. Maximal means no individual extension is allowed; maximum means largest size or best weight according to a declared objective. These notions coincide in cardinality for matroid bases, but not for arbitrary hereditary families. Graphic matroids take forests as independent edge sets; vector matroids take linearly independent indexed columns, including distinct indices for repeated equal vectors.

To maximize basis weight, process elements in nonincreasing weight order and add an element whenever independence is preserved. Continue through all elements, even negative-weight ones if a full basis is required. The exchange proof maintains an optimal basis containing the current greedy prefix. If the next accepted element g is absent from that basis, a basis-exchange consequence lets us replace some element outside the prefix by g while retaining a basis. An earlier accepted element belongs to the preserved prefix. An earlier rejected element is dependent with a subset of that prefix, so it cannot belong to a basis containing the prefix. The removed element must therefore occur later in the ordering, with weight no larger than g's.

The exchanged basis therefore has no smaller total weight, and it contains the extended prefix. Repeating gives an optimal greedy basis. For maximum-weight independent sets without a full-basis requirement, discard negative-weight elements or stop before them; adding a negative element could lower the objective. Nonnegative weights allow extending an optimum to a basis without reducing weight. These variants are easy to conflate, so state whether rank completion is compulsory before describing the algorithm.

Matchings in an arbitrary graph form a hereditary edge family, but generally not a matroid. On the four-vertex path a−b−c−d, the singleton middle edge is a maximal matching, while the two outer edges form a larger matching. Neither outer edge can augment the singleton because each touches the middle edge. Thus augmentation fails. Assigning the middle edge weight three and each outer edge weight two makes descending-weight greedy earn three while an alternative earns four.

The matroid theorem does not claim every successful greedy algorithm comes from a matroid. Earliest-finish interval scheduling is a different objective-specific exchange argument. Nor does a mathematical independence oracle automatically yield a fast implementation: the number and cost of independence tests matter. For a graphic matroid, disjoint-set structures test whether an edge closes a cycle efficiently, producing Kruskal's minimum-spanning-forest rule with ascending costs, and a spanning tree when the graph is connected. For vector matroids, elimination supplies independence tests whose arithmetic and numerical interpretation must be specified.