Hodge theory in combinatorics
Matthew Baker · Open research survey
Read Baker §§2.3 and 2.6–2.7 for rank, closure and flats; calculate K₃ alongside the definitions.
Open the sourceBases, circuits, rank and flats
Four views of the same dependence structure.
Prerequisites: 15 · Matroids: independence without coordinates
Understand
Objectives
- Calculate rank and closure on the fixed K₃ edge ground set.
- List all flats, bases and circuits without equating them.
- Check a submodular diminishing-gain comparison.
Start with something you can see
Fix the ground set to the three edges of K₃: a=1–2, b=2–3, c=1–3. Select path {a,b}. Predict whether adding c adds a new independent edge: it closes a cycle, so rank remains two. The third edge belongs to the path’s closure even though it was not selected. The table works without a new lab.
Give the idea a precise name
For a matroid on E, rank r(S) is the largest size of an independent subset of S. A basis is a maximal independent subset of E; a circuit is a minimal dependent subset. Closure collects elements that do not raise rank: cl(S)={e∈E:r(S∪{e})=r(S)}. A flat equals its own closure. Closure is always relative to the fixed ground set E; an element outside E cannot appear in it.
r(A)+r(B)≥r(A∪B)+r(A∩B)
This is rank submodularity for subsets A,B⊆E. Equivalently, if A⊆B and e∉B, the rank gained by adding e to A is at least the gain from adding it to B. Both increments are zero or one. The graph rank of a selected edge set S is the number of vertices minus the number of components of (V,S).
Work one small world
In K₃, r(S)=min(|S|,2). The full set E is the sole circuit, and each pair is a basis. Check all eight subsets rather than inferring closure from a drawing:
| S⊆E | r(S) | cl(S) | Flat? |
|---|---|---|---|
| ∅ | 0 | ∅ | yes |
| {a}, {b}, {c} | 1 each | same singleton each | yes each |
| {a,b}, {a,c}, {b,c} | 2 each | E each | no |
| E={a,b,c} | 2 | E | yes |
Thus the flats are ∅, the three singletons and E; a basis need not be a flat. For A={a} and B={a,b}, adding c raises r(A) from one to two, but leaves r(B) at two. This is the diminishing-rank gain stated above.
Counterexample to “every independent set is a flat”: {a,b} is independent and maximal, yet cl({a,b})=E. The omitted edge c is dependent on that pair. Conversely, E is a flat but is dependent; flatness and independence answer different questions.
THE BRIDGEThe flats of K₃ form a five-element inclusion lattice, the input to the next polynomial calculation.
WHERE THIS IDEA STOPSThe closure of S is not its complement. The greedy weight theorem needs the matroid axioms and a specified weight objective, not merely this rank table.
Experiment
Use the polytope lab’s fixed K₃ edge set {a,b,c}. Start with path {a,b}, predict closure before adding c, then select each basis and read its indicator. Interior point uses weights 0.2, 0.3, 0.5; it is not a new basis or a change of ground set.
Which elements add no new rank to the set already in your hand?
Check & explain
How many bases does the K₃ graphic matroid have?
What is cl({a,b}) for K₃ edges E={a,b,c}?
- {a,b}
- E
- ∅
Teach back
Compute every closure for K₃, then change to U₂,₄: predict the number of bases and whether a pair is a flat.
- Keep the ground set fixed.
- Use rank equality for every closure test.
- For U₂,₄, find six bases and no pair flats.
Read deeper
Lecture Notes · Topics in Combinatorial Optimization
MIT OpenCourseWare · Course notes · MIT OCW
Read lecture 14 notes on strong basis exchange after computing the triangle flats.
Open the source