Hodge theory in combinatorics
Matthew Baker · Open research survey
Read Baker §2.1 for the independence axioms; test each one on U₂,₃.
Open the sourceMatroids: independence without coordinates
Keep the rules of good selections; forget the original drawing.
Prerequisites: 07 · Independence: when a choice adds something, 14 · The first exact bridge: graph → matrix
Understand
Objectives
- Name the ground set and all three independent-set axioms.
- Test augmentation with explicit smaller and larger sets.
- Find a hereditary near-miss and show both failed additions.
Start with something you can see
Keep the triangle edges a=1–2, b=2–3, c=1–3. The smaller forest I={a} and the larger forest J={b,c} do not contain one another. Predict which edge of J can enlarge I without forming a cycle. Test both rather than assuming one arbitrary edge works.
Give the idea a precise name
A finite matroid is a finite ground set E with a family 𝓘 of independent subsets. It obeys three axioms: ∅∈𝓘; every subset of an independent set is independent; and a smaller independent set can gain some element from a larger one while remaining independent. The first two axioms alone are not enough. A graphic matroid takes E to be graph edges, not vertices. Vector matroids come from columns, but general matroids need not be representable by vectors over any field.
I,J∈𝓘, |I|<|J| ⇒ ∃e∈J∖I with I∪{e}∈𝓘
The symbol 𝓘 is the family of allowed subsets of E, not a single subset. The sizes |I| and |J| count elements; J∖I names candidates absent from I; ∃ says at least one works, not that every choice works. All bases have equal size because a smaller maximal independent set would contradict augmentation.
Work one small world
For the triangle, every edge pair is a forest, but all three edges form one circuit. Test the two candidates explicitly:
| I | J | Try e∈J∖I | I∪{e} | Independent? |
|---|---|---|---|---|
| {a} | {b,c} | b | {a,b} | yes |
| {a} | {b,c} | c | {a,c} | yes |
| {a,b} | {a,c} | none required | equal sizes | axiom not triggered |
The maximal forests {a,b}, {a,c}, {b,c} are the three bases of U₂,₃. Graph and vector descriptions share this family of allowed edge selections.
Counterexample to “hereditary implies matroid”: let E={a,b,c} and 𝓘={∅,{a},{b},{c},{a,b}}. Every subset of an allowed set remains allowed. But I={c} and J={a,b} are both allowed, |I|<|J|, and neither {a,c} nor {b,c} belongs to 𝓘. Augmentation fails on both candidate steps.
THE BRIDGERank, closure and flats are derived from the independent-set family rather than added as unrelated structure.
WHERE THIS IDEA STOPSHereditary constraints alone need not be matroids; no general vector representation is promised.
Experiment
Cover the final column of the table, test b and c by drawing the selected edges, then compare the failed near-miss attempts.
What guarantees that a smaller good selection can borrow something from a larger good selection?
Check & explain
For 𝓘={∅,{a},{b},{c},{a,b}}, which axiom fails?
- Empty set
- Heredity
- Augmentation
How many maximal independent edge sets does the triangle have?
Teach back
Test the triangle and near-miss side by side. State a particular augmentation witness in one and show every candidate fails in the other.
- State E and 𝓘 before testing.
- Distinguish ∃e from “every e.”
- Use both attempted additions in the near-miss.
Read deeper
Matroid Theory, 2007 course notes
Federico Ardila · Free author course
Use Ardila lectures 1–7 for graphic and linear examples; find the basis-exchange discussion.
Open the sourceLecture Notes · Topics in Combinatorial Optimization
MIT OpenCourseWare · Course notes · MIT OCW
Read lecture 9 notes for matroid definitions and representability.
Open the source