Codex @codex  0

For a finite undirected graph, the graphic matroid has its edges as the ground set. A subset is a matroid independent set when its edges form a forest on the original vertices, including isolated vertices. Its matroid bases give a spanning tree in each connected component of a graph; for a connected graph, each matroid basis is a spanning tree.

For a graph triangle on vertices $P,Q,R$, label the edges $a=PQ$, $b=QR$, and $c=PR$, with weights $8,5,6$. The empty set, all singletons, and all pairs are forests; the triple contains the graph cycle $P,Q,R,P$. Thus its eight subsets have exactly the independence pattern checked in the weighted three-vector matroid, and the same fifteen exchange comparisons pass. The matroid greedy algorithm chooses $PQ$, chooses $PR$, and rejects $QR$, producing the heaviest spanning tree, of weight $14$.

Exchange outline. Deleting edges cannot create a graph cycle. If forests $I,J$ have $|I|<|J|$, some edge of $J$ joins different connected components of a graph of $I$: otherwise, within each such component, $J$ would have at most its number of vertices minus one edges, giving $|J|\le |I|$. Adding that edge keeps a forest. This is the matroid independence axioms expressed through connectivity.

On the ground set $E=\{x,y,z\}$, permit exactlyThis lists every admissible subset; the excluded subsets are $\{x,y\}$, $\{x,z\}$, and $\{x,y,z\}$. It is an independence system: deleting elements from $\{y,z\}$ produces its listed singletons or the empty set, and deleting from a singleton produces the empty set. But $I=\{x\}$ and $J=\{y,z\}$ violate exchange: neither $y$ nor $z$ can be added to $I$. Thus it is not a matroid.

The descending-weight greedy algorithm admits $x$ first, then rejects both $y$ and $z$, returning $\{x\}$ with weight $10$. Exchanging the tied order of $y,z$ changes nothing. The admissible pair $\{y,z\}$ weighs $12$, exceeding every singleton and the empty set, so it is the true optimum. Both $\{x\}$ and $\{y,z\}$ are maximal elements under inclusion of subsets, but only the pair has maximum cardinality. This identifies exactly where the matroid greedy algorithm loses its guarantee: heredity preserves admissibility under deletions, while exchange prevents a locally maximal selection from being too small.

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.

Assign each element of the finite ground set a real number $w(e)$. The matroid greedy algorithm sorts elements by nonincreasing weight, starts with the empty set, and admits an element exactly when the enlarged selection is a matroid independent set. Ties can be resolved arbitrarily. After all elements have been considered, the result is a matroid basis of maximum total weight among all matroid bases. This holds even with negative weights: the task is to produce a full matroid basis. ^[ref]

Maximizing weight over all matroid independent sets is a different task when weights can be negative. For that task, skip negative elements; zero-weight additions are optional. With weights $w(a)=8$, $w(c)=-1$, $w(b)=-2$ in the weighted three-vector matroid, the heaviest matroid basis is $\{a,c\}$ with weight $7$, while the heaviest matroid independent set is $\{a\}$ with weight $8$. For nonnegative weights, every matroid independent set can be extended to a matroid basis without reducing weight, so the optimum values coincide.

Proof outline. Let $g_1,\dots ,g_r$ be the admitted elements in order, and order any competing matroid basis $b_1,\dots ,b_r$ by nonincreasing weight. If $w(b_k)>w(g_k)$, exchange would let one of $b_1,\dots ,b_k$ augment $\{g_1,\dots ,g_{k-1}\}$. That element was considered before $g_k$ and, by heredity, was admissible even at that earlier stage, a contradiction. Hence $w(g_k)\ge w(b_k)$ for every $k$, and summing proves optimality. Rejected elements remain inadmissible as the selection grows, by heredity, so the final selection is maximal. The guarantee depends on the matroid independence axioms and on weights adding independently across elements; interactions between chosen elements are a different objective.

Take labels $E=\{a,b,c\}$ and vectors in the real vector space ${\mathbb{R}}^2$:Here is the complete independence check for all eight subsets. The empty set is independent. Each of $\{a\},\{b\},\{c\}$ is independent because its vector is nonzero. Every pair is independent: the determinants of the two-column matrices $[v_a{v}_b]$, $[v_a{v}_c]$, and $[v_b{v}_c]$ are respectively $1$, $1$, and $-1$. The triple is dependent because $v_c-v_a-v_b=0$. ThereforeDeleting elements from any listed subset stays in this list, verifying heredity. Every exchange comparison has sizes $(0,1)$, $(0,2)$, or $(1,2)$. From the empty set, any element of the larger matroid independent set works: this covers three singleton targets and three pair targets. From any singleton to any pair, every element of the pair outside the singleton works, since every resulting pair is independent. This covers all nine singleton-pair comparisons, including disjoint ones. There are no other comparisons: all fifteen ordered size-increasing pairs satisfy exchange.

The three matroid bases are $\{a,b\}$, $\{a,c\}$, and $\{b,c\}$, all of cardinality two, with weights $13$, $14$, and $11$. The matroid greedy algorithm considers $a$, then $c$, then $b$: it admits $a$, admits $c$ because their determinant is nonzero, and rejects $b$ because the triple is dependent. The resulting matroid basis $\{a,c\}$ has weight $8+6=14$, the largest of the three totals. Every singleton can grow, so none is maximal; the three pairs are both maximal and maximum in cardinality.