Rado and Edmonds: greedy is optimal for every weight function exactly when the family of feasible sets is a matroid. Both directions matter and the second is the one with teeth — a family that is not a matroid always has a weighting on which greedy loses. The lab does not quote that; it searches {1, 2, 3}ⁿ and returns the first weighting that works, which on the three-element non-matroid is the thirteenth of twenty-seven.
Core ideas
Three ideas: what quantifying over weightings changes, why the converse is the useful half, and why a search that stops at the first counterexample is the right thing for a panel and the wrong thing for a check.
Greedy can be optimal on a non-matroid for a particular weighting, and often is. On the matchings of a path with weights 3 1 3 the ends are heaviest, greedy takes both, and it is optimal. The theorem is not about a weighting; it says the family is a matroid exactly when no weighting defeats greedy. A single successful run tells you about that run.
“Matroid implies greedy works” licenses an algorithm. “Greedy works for all weightings implies matroid” is what lets you rule a problem out: show that the feasible sets have two maximal sets of different sizes and you have proved that some weighting defeats every greedy rule of this shape, without having to find it. The lab then finds it anyway, because a counterexample you can read is worth more than one you know exists.
beatingWeights walks {1, 2, 3}ⁿ in a fixed order and stops at the first weighting where greedy loses, reporting how many it tried. That is right for a reader: it makes the counterexample reproducible. It is wrong as a check, because stopping early cannot establish that a matroid has none — for that the whole space has to be walked, and on five elements that is 243 weightings.
The material
Both directions with proofs, the counterexample search, and the reason the number thirteen on this page is a fact about a walk order rather than about matroids.
Given an independence system (E, I) and non-negative weights w, sort E in decreasing weight and walk it once, adding each element when the set so far plus that element is still independent. The result is a maximal independent set; the question is whether it is a maximum-weight one.
Let (E, I) be an independence system. Greedy returns a maximum-weight independent set for every non-negative weight function w if and only if (E, I) is a matroid.
Suppose first that (E, I) is a matroid and let G be greedy's answer and O a maximum-weight independent set. Both are bases, so they have the same size r. List each in decreasing weight, g₁ ≥ g₂ ≥ … ≥ g_r and o₁ ≥ o₂ ≥ … ≥ o_r. The claim is that w(gᵢ) ≥ w(oᵢ) for every i, which gives w(G) ≥ w(O) at once.
Suppose not, and take the least i with w(gᵢ) < w(oᵢ). Let A = {g₁, …, g_(i−1)} and B = {o₁, …, oᵢ}, both independent by downward closure, with |A| < |B|. By the exchange property some x in B \ A has A ∪ {x} independent, and w(x) ≥ w(oᵢ) > w(gᵢ). But greedy, having chosen A, would have reached x before gᵢ and taken it. Contradiction.
For the converse, suppose the exchange property fails for some independent A and B with |A| < |B|, chosen with |A| as large as possible among failures, and write a = |A|. Give every element of A weight a + 2, every element of B \ A weight a + 1, and everything else weight 0. Greedy takes all of A first, then can add nothing from B \ A by assumption, so it collects at most a(a + 2) from the weighted elements; B alone is worth at least (a + 1)², which is larger. So greedy is not optimal for that weighting.
□
The converse is constructive, which is worth noticing: it does not merely assert that a bad weighting exists, it builds one out of the failing pair. On the matchings of a path with A = {B} and B = {A, C}, that recipe gives the middle edge weight 3 and the two ends weight 2 each, and greedy takes the middle for 3 against 4.
Which is exactly the weighting the lab ships as that family's default: 2 3 2. Greedy takes the middle edge, worth 3, and the best independent set is the pair of ends, worth 4. So the reader meets a counterexample before reading the proof that guarantees one, and the panel reports the gap as a measurement rather than as an illustration.
The panel then does something the proof does not: it walks every weighting in {1, 2, 3}ⁿ in a fixed order and stops at the first one on which greedy is beaten. On the three-element family that space has 27 weightings, and the search stops after 13 of them, at 1 2 2. Greedy takes the middle edge for 2; the two ends are worth 3 together.
Thirteen is a fact about the enumeration order and nothing else. It is not a measure of how badly the family fails, not a property of matroids, and not stable under relabelling the elements. What is a fact about the family is that the search terminates at all, which the converse guarantees for every non-matroid, and that its answer is a concrete triple a reader can type back into the weights box.
On each of the three families that are matroids the panel walks the whole space: all 3⁵ = 243 weightings in {1, 2, 3}⁵, with greedy compared against the best member of the family on each. None of the 243 beats greedy on the uniform family, none on the graphic family, none on the partition family. The panel reports that it tried all of them, because “no counterexample found” and “the whole space was searched” are different sentences and only the second is worth printing.
It is still a sample. {1, 2, 3}ⁿ is 243 of the infinitely many weight functions on five elements, and a family could in principle survive all of them and fail on {1, 2, 4}. The theorem is what rules that out, and the sweep is what would catch an implementation that had drifted away from the theorem. Neither replaces the other.
One detail of the sweep is worth a sentence because it decides a tie. With weights 1 2 2 the two heaviest elements are tied, and greedy takes the middle edge rather than an end. Change the order in which ties are broken and greedy would take an end, then the other end, and reach 3 — the optimum. A counterexample to a greedy rule can depend on the tie-break, and the panel's is fixed, stated by the trace it prints, and part of the algorithm rather than an accident of it.
Measured on this page: 27 weightings in the space for the matchings family, 13 tried before one beat greedy, 1 2 2, giving 2 against 3; 243 weightings each for the three matroids, all tried, none beating greedy. Proved on this page: greedy is optimal for every non-negative weight function exactly when the family is a matroid. The sweep is 243 points and the theorem is every point, and this is the page on the course where that gap is smallest and still absolute.
Interactive
The exchange property on every pair, and the weighting that beats greedy when it fails
Method
Four steps. The first two decide the question; the last two are what make the answer usable by someone else.
The theorem is about (E, I). Weights are a separate input and the whole content of the statement is that they do not matter when the family is a matroid. A problem description that mixes the two — “pick the heaviest non-conflicting set” — hides the object being tested.
A matroid needs no further argument: greedy is optimal for every weighting, including ones nobody will ever supply. This is the direction that licenses an algorithm, and it is the reason the previous page's pair test is worth running.
The converse's recipe is explicit: weight A at |A| + 2, weight B \ A at |A| + 1, weight everything else 0. On the matchings of a path that gives 2 3 2, which is the family's shipped weighting and beats greedy by 3 to 4.
“Some weighting defeats greedy” is a citation. “Weights 1, 2, 2 give greedy 2 where the optimum is 3” is a counterexample a reader can check in ten seconds. The panel prints the second and prints how much of the space it had to look at to get there.
The family: subsets of A = 1-2, B = 2-3, C = 3-4 with no two edges sharing a vertex. Independent sets: {}, {A}, {B}, {C}, {A,C}. The exchange property fails on {B} against {A,C}.
The last line is the one to keep. Greedy is optimal on the non-matroid for the weighting 3 1 3, and for many others: of the 27 weightings in the search space, the walk had to pass twelve before finding a failure. A reader who typed one weighting and saw greedy win would have evidence for the wrong conclusion, and that is the entire reason the theorem quantifies.
Notice also that the two counterexamples differ. The proof's recipe produces 2 3 2 and a gap of 3 against 4; the search produces 1 2 2 and a gap of 2 against 3. Both are valid and neither is canonical: what the theorem guarantees is that the set of bad weightings is nonempty, not that it has a distinguished member.
For a faded rehearsal, apply the recipe to the matchings of a four-edge path, 1-2, 2-3, 3-4, 4-5. The supplied first move is to find a failing pair: {B, D} is maximal with two elements, and {A, C} extends — look for a pair where the smaller side cannot be grown. Write down the weighting the recipe gives, predict greedy's answer and the optimum, then check both in the panel by typing the edge list and the weights.
You should be able to state the theorem with its quantifier in the right place, reproduce the exchange argument that proves the forward direction, build a bad weighting from a failing pair using the converse's recipe, and explain why a weighting on which greedy wins over a non-matroid is not evidence of anything.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.