Three of the algorithms on this course are greedy and optimal, each proved its own way. There is a single condition on the family of feasible sets that explains all three, and it is not “the problem looks like scheduling”. The lab gives four families as membership tests, lists each by asking the test about every subset, and then tests the exchange property on every ordered pair of independent sets. Three of the four pass. One does not, and it is the one with three elements.
Core ideas
Three ideas: why a family is given by a test rather than by a list, what downward closure buys before the exchange property is even asked about, and what the exchange property actually says.
An independence oracle answers one question: is this set independent? The four families here are exactly that — a rank test, a cycle test, a one-per-group test, a shared-vertex test — and the panel produces the family by asking the oracle about all 2ⁿ subsets. Nothing is labelled a matroid anywhere in the kit; the family is enumerated from the test, and the properties are then checked on what came out.
Greedy needs to be able to stop. If dropping an element from a feasible set could make it infeasible, then a rule that adds elements one at a time has no invariant to maintain. Downward closed says every subset of an independent set is independent, and it is what makes the family an independence system. All four families here satisfy it, including the one that is not a matroid, so it is genuinely the weaker condition.
If A and B are independent and A is strictly smaller than B, then some element of B not already in A can be added to A keeping it independent. Note what it does not say: not that any particular element works, not that A can be grown to B's size in one step, and not that A is contained in anything. The panel tests every ordered pair with |A| < |B|, which is 193 pairs on the opening family and 7 on the smallest one.
The material
The definitions, the four families given as oracles, what the exchange test finds, and why the graphic case is a course you have already taken.
A pair (E, I) where E is a finite ground set and I is a collection of subsets of E, called independent, such that I is nonempty and downward closed: if B is in I and A ⊆ B then A is in I. A maximal independent set is called a basis; the size of a largest one is the rank.
An independence system (E, I) satisfying the exchange property: whenever A and B are independent with |A| < |B|, there is an element x in B but not in A such that A ∪ {x} is independent.
One consequence is worth stating immediately, because it is what the counterexample later violates: in a matroid every basis has the same size. If two maximal independent sets had different sizes, the exchange property applied to the smaller and the larger would produce an element extending the smaller one, contradicting its maximality.
The lab opens on the forests of a four-vertex graph with edges 1-2, 2-3, 3-1, 3-4, 1-4, labelled A to E in that order. A set of edges is independent when it contains no cycle. The oracle is asked about all 32 subsets and accepts 24 of them; the rank is 3, there are 8 bases, and the family is downward closed — dropping an edge from a forest leaves a forest.
The panel forms every ordered pair (A, B) of independent sets with |A| < |B| — 193 of them on this family — and for each asks whether some element of B can join A. Every one of the 193 succeeds, so the forests of this graph form a matroid. The 8 bases are its spanning trees, and every one of them has 3 edges, which is |V| − 1 for a connected graph on four vertices.
Sort the elements by weight and add each one if it keeps the set independent. On the forests of a graph that is Kruskal's algorithm. The one difference from the version proved in the graph course is the direction: matroid greedy maximises, so it sorts heaviest first and builds a maximum spanning tree. With weights 8 6 5 4 2 it takes A, takes B, rejects C because 1-2, 2-3 and 3-1 would close a cycle, takes D, rejects E, and finishes with {A, B, D} worth 18 — the best any independent set can do.
That is the point of the whole construction. The cut property gave a proof of Kruskal that is about graphs: lightest edge crossing a cut, cycles, connectivity. The matroid theorem gives a proof that is about the family of feasible sets and mentions no graph at all, and the same proof then covers families that have nothing to do with graphs.
The uniform family takes every subset of at most k elements from a ground set of five. With k = 2 that is 16 sets, rank 2, and all 10 pairs are bases; 65 ordered pairs are tested and none fails. The partition family allows at most one element from each group; with groups 1 1 2 2 3 that is 18 sets, rank 3, 4 bases, 109 pairs, and no failure. Greedy with weights 7 6 5 4 3 takes the heaviest element of each group, {A, C, E}, worth 15.
Ground set: the three edges 1-2, 2-3, 3-4 of a path, labelled A, B, C. A set is independent when no two of its edges share a vertex. The oracle accepts 5 of the 8 subsets: the empty set, each single edge, and {A, C}. The family is downward closed. Of the 7 ordered pairs tested, exactly one fails: A = {B} and B = {A, C}. Neither end can join the middle edge, because each shares a vertex with it.
So this family has two maximal independent sets of different sizes: {B}, which cannot be grown, and {A, C}, which is the only basis. That is the same statement as the exchange failure, and it is the first place on this course where the shape of the feasible family, rather than the rule, is what goes wrong.
It is also the smallest possible instance. Two elements cannot produce a failure — with |A| < |B| ≤ 2 and downward closure, the singleton inside B is available — so three elements is where a non-matroid independence system can first appear, and a path with three edges is the one everybody meets first.
Measured on this page: 24 independent sets of 32 for the forests, rank 3, 8 bases, 193 exchange pairs and 0 failures; 5 independent sets of 8 for the matchings, 7 pairs and 1 failure. Proved on this page: in any matroid all bases have the same size, which the matchings family visibly violates. What is not on this page is the reason any of this predicts whether greedy works — that is a theorem in both directions, and it is next.
Interactive
The exchange property on every pair, and the weighting that beats greedy when it fails
Method
Four steps, in this order. The second catches more candidate families than the third does.
A family is only as clear as the predicate that defines it. “Edge sets with no cycle”, “at most one from each group”, “no two sharing a vertex”: each is a test you can apply to a set handed to you, and the list follows from it rather than the other way round.
It is cheaper than the exchange test and it fails more often in practice. If removing an element can break feasibility, the family is not an independence system and no greedy rule has an invariant to maintain. All four families in the lab pass this and one of them still fails the next step, which is why they are separate conditions.
This is the fast way to refute the exchange property by hand. Any independence system with two maximal independent sets of different sizes fails it, and the smaller one is half of the counterexample. On the matchings family, {B} is maximal with one element and {A, C} is maximal with two.
The full test is quadratic in a family that is itself exponential, which is why the panel caps the ground set at six elements and says so. When it runs, it reports the number of pairs tested and lists the failures, so a passing family comes with the size of the evidence attached.
Ground set A = 1-2, B = 2-3, C = 3-4. A set of edges is independent when no two of them share a vertex. There are eight subsets; test each.
Two maximal independent sets of different sizes is the whole failure, said twice. The set {B} cannot be extended and is not a basis, so “maximal independent set” and “maximum independent set” are different things here — and in a matroid they are the same thing, which is why the distinction never came up on the previous page.
The uniform, graphic and partition families all pass the same test: 65, 193 and 109 ordered pairs respectively, with no failures. Three passes and one failure on four families is not a survey; what makes the failure interesting is that the theorem coming next makes it predictive rather than merely true.
For a faded rehearsal, work out the independent sets of the matchings of a four-edge path, 1-2, 2-3, 3-4, 4-5, before running it. The supplied first move is that {A, C}, {A, D} and {B, D} are all independent and none of the three can be extended, so on that path every maximal independent set does have the same size. Say how many independent sets there are in all, how many ordered pairs the exchange test forms, and whether the property still fails — and then say which single edge you could delete to turn the family into a matroid.
You should be able to state both axioms, list a small family from its oracle, produce the two maximal sets of different sizes when a family fails, explain why matroid greedy on the forests of a graph is Kruskal with the sort reversed, and say what downward closure buys before the exchange property is asked about.
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.