Some greedy proofs depend on the structure of feasible sets rather than on a particular picture of intervals or graphs. A matroid captures one such structure. We will prove a maximum-weight theorem and see precisely why negative weights require care when the goal changes.
Independence and augmentation
Definition 6.1.1
(Matroid, independent set and basis)
A finite matroid is a finite ground set together with a nonempty collection satisfying two conditions.
- Hereditary: if and , then .
- Augmentation: if and , some has .
Members of are called independent. A basis is an inclusion-maximal independent set. The empty set is independent by nonemptiness and heredity.
These facts concern inclusion, not weights.
Lemma 6.1.2
(Bases have equal size and independent sets extend)
In a finite matroid, any two bases have the same number of elements, and every independent set is contained in a basis.
Proof
(Augmentation against maximality)
Let be bases with . Augmentation gives with independent, which contradicts the maximality of . Hence , and by symmetry the sizes are equal.
Let be independent. If is not maximal, some independent proper superset exists; replace by it. Each replacement increases the size, and the size never exceeds , so after finitely many steps is maximal, that is, a basis containing the original set.
Greedy by decreasing weight
Give each element a real weight and write . Sort all elements in nonincreasing weight order, with , breaking ties by any fixed rule. Start with and scan in order; add an element exactly when the enlarged set is independent. Scan even negative-weight elements. Write for the prefix of the first elements and for what has been selected from it.
Theorem 6.1.3
(Greedy returns a maximum-weight basis)
For arbitrary real weights, the set produced by the scan is a basis, and for every basis .
Proof
(Maximality, then a prefix comparison)
is a basis. is independent because it starts empty and an element is added only when independence is kept. Suppose . When was scanned, the current set satisfied . Since , if were independent then heredity would make independent. So no element can be added to , and is maximal.
Each prefix is handled optimally. The same argument shows that is maximal independent in : an element of rejected earlier cannot become feasible after has grown. If some independent had , augmentation would give with independent, contradicting maximality. So has maximum cardinality among independent subsets of .
Comparison with a basis. Let be any basis, with elements in sorted order, so with . By the lemma, also has elements in sorted order, . The set is independent by heredity, so . Therefore the th selected element appears no later than position : . Because the order is nonincreasing, for each . Summing over gives . Ties, negative weights and (both sums are zero) are all covered.
Proof X-ray
Where each hypothesis enters
The proof uses the two axioms in specific, separate places. Heredity appears twice: once to show that a rejected element stays rejected as grows, and once to see that the first elements of form an independent subset of a prefix. Augmentation appears exactly once, to upgrade "maximal in " to "largest possible size in ". The equal-size lemma, itself a consequence of augmentation, is what makes the sums over and have the same number of terms.
The non-obvious move is to compare prefix by prefix rather than set against set. The inequality turns a statement about weights into a counting statement about independent sets, and the sorted order then converts "appears no later" into "weighs at least as much". The argument closes termwise: each of the pairs satisfies , so the sums compare.
Notice what is never used: the sign of a weight. Only the sorted order enters, which is why negative weights are harmless for bases. What does break the argument is a failed axiom, as the hereditary example below shows.
Thus greedy returns a maximum-weight basis for arbitrary real weights. It need not return the only optimum. A straightforward implementation costs comparisons to sort plus independence tests; the cost of a test depends on the representation of the matroid.
Quick check
(Can the greedy basis theorem use negative weights?)
Look at which property of the weights the proof uses.
Solution · Answer
Yes. It still maximizes among bases, because the proof compares equal-length sorted weight lists and only uses the order of the weights, never their sign.
Worked examples
Worked example 6.1.4
(A partition matroid)
Suppose has red elements of weights and blue elements of weights . Let a set be independent when it contains at most one red and at most one blue element. Heredity is immediate. For augmentation, if , then uses some color absent from ; an element of that color in augments . Greedy scans , selecting of total weight . The remaining elements would repeat a color. This is a maximum-weight basis, and here it is also a maximum-weight independent set.
Worked example 6.1.5
(Ties and a negative weight)
Let with every set of at most two elements independent. Heredity is clear; if , any keeps the size at most . Take and , with ties broken as before . Greedy accepts , then (the set has two elements), and rejects . The output has weight .
Check against all bases, which are the three -element sets: , , . The maximum is , attained twice. Breaking the tie the other way returns , a different set of the same weight.
Worked example 6.1.6
(A loop is never selected)
Let with independent sets and only; the element is a loop, because is dependent. Hereditary holds, and augmentation holds because the only pair is , , where augments. Let and . Greedy scans first and rejects it, since is dependent; it then accepts . The output has weight , and it is the only basis, so it is optimal even though a heavier element exists. If were also a loop, the only basis would be with and weight .
Counterexample mode
A basis is not always the best independent set
Take a one-element ground set with both and independent, and weight . The only basis is , so greedy returns weight . But among all independent sets the empty set has weight . If all weights are nonnegative, every independent set extends to a basis without decreasing weight; then the maximum-weight basis is also a maximum-weight independent set. With arbitrary signs, the two objectives differ.
Common mistakes
Common mistake
(Skipping the negative-weight elements)
It is tempting to stop scanning once the weights turn negative. For the basis problem this is wrong. In the example with , , stopping before returns , which is independent but not a basis, since can still be added. The theorem is about bases, so every element must be scanned. Maximizing over all independent sets is a different problem.
Common mistake
(Expecting a unique optimum)
The theorem gives the optimal weight, not a unique optimal set. In the example above, and both have weight , and the output depends on the tie-breaking rule. Any rule works, but the returned set is not canonical.
Heredity alone is not enough
Heredity is easy to check locally, so one might hope that greedy is optimal for every hereditary system. The augmentation axiom is exactly what the proof needed, and without it the claim fails.
Counterexample mode
A hereditary system that is not a matroid
Let and let the independent sets be all subsets of or of . This system is hereditary but not a matroid: and violate augmentation. With weights , , descending greedy takes and cannot take either remaining element, giving weight ; has weight . A local feasibility check is not itself a proof of global optimality.
Exercises
Quick check
(In the partition example, what happens if the blue weight is changed to ?)
Re-sort the four elements first.
Solution · Answer
The sorted order becomes . Greedy selects that blue element and , with total weight ; and repeat colors.
Quick check
(Why can an element rejected on a prefix not become feasible later?)
Use heredity on the earlier selected set.
Solution · Answer
If it were feasible with a larger selected set, heredity would make it feasible with the earlier subset, where it was rejected.
Quick check
(What is the maximum-weight independent set in the one-element negative example?)
Compare with .
Solution · Answer
, of weight , since has weight .