Hodge theory in combinatorics
Matthew Baker · Open research survey
Read Baker §§3.2–3.3 after the §2 flat definitions; reconstruct the U₂,₃ sum.
Open the sourceThe lattice and characteristic polynomial
Generalize the graph invariant using only dependence.
Prerequisites: 16 · Bases, circuits, rank and flats, 17 · Graph coloring becomes a polynomial
Understand
Objectives
- Calculate Möbius values from the flat inclusion order.
- Compute χ and χ̄ with the correct rank and division.
- Relate chromatic and characteristic polynomials with the component factor.
Start with something you can see
Take the K₃ edge matroid U₂,₃ from lesson 16, with E={a,b,c}. Its closed sets are ∅, three singletons and E. Predict the alternating number attached to E if the numbers below it must sum to zero. The inclusion diagram shows the whole lattice; a pair is absent because its closure is E.
Give the idea a precise name
A flat is a set equal to its closure; the flats form a lattice ordered by inclusion. For a loopless matroid of rank R, the least flat is ∅. Define the Möbius value μ(∅,∅)=1 and, for a nonempty flat F, choose μ(∅,F) so that the values over flats G⊆F sum to zero. Weight each flat by a power determined by its rank to form the characteristic polynomial.
μ(∅,F)=−Σ_{G⊊F}μ(∅,G); χ_M(q)=Σ_F μ(∅,F)qR−r(F)
The sum is over flats, not all subsets. R is matroid rank, r(F) is the flat’s rank, and the exponent R−r(F) is zero at the top flat. For a graph with c components, P_G(q)=qᶜχ_{M(G)}(q). For a nonempty loopless matroid, χ_M(1)=0 and the reduced polynomial is χ̄_M(q)=χ_M(q)/(q−1). These are distinct normalizations.
Work one small world
The Hasse diagram draws only immediate inclusion relations: ∅ at rank zero, the three singleton flats at rank one, and E at rank two. Their Möbius values are 1, −1 each, and 2 at E because 1−1−1−1+2=0.
| Flat F | r(F) | μ(∅,F) | Term |
|---|---|---|---|
| ∅ | 0 | 1 | q² |
| {a}, {b}, {c} | 1 each | −1 each | −3q total |
| E | 2 | 2 | 2 |
Therefore χ(q)=q²−3q+2=(q−1)(q−2), and χ̄(q)=q−2. For the 4-cycle, P=qχ with χ=q³−4q²+6q−3=(q−1)(q²−3q+3); its reduced absolute coefficients are (1,3,3), not the coefficients of P.
Counterexample to dividing by q for every graph: attach an isolated vertex to the triangle. The graph then has two components and P=q²χ, not qχ. Its edge matroid is still U₂,₃: the isolated vertex contributes no edge to the ground set. Also do not form χ̄ by dividing blindly for an empty or looped matroid; the stated reduced convention assumes nonempty and loopless.
THE BRIDGEReduced coefficients become mixed degrees in a graded ring; the coefficient identity and its Hodge inequality are later theorems, not consequences of this diagram.
WHERE THIS IDEA STOPSLoopless and nonempty are hypotheses for the stated reduced polynomial. The rank-two example does not establish coefficient inequalities for every matroid.
Experiment
Cover the μ column of the table, calculate from ∅ upward, and compare each new value with the diagram. Then contrast the 4-cycle polynomial lines.
Which correction is required so that the Möbius values below each nonempty flat sum to zero?
Check & explain
For U₂,₄, what is the Möbius value of the top flat?
Which is χ̄ for the 4-cycle matroid?
- q²−3q+3
- q³−4q²+6q−3
- q⁴−4q³+6q²−3q
Teach back
Build the flat lattice of U₂,₄ and compute its Möbius values, χ and χ̄. Explain why an isolated graph vertex changes P but not the edge matroid.
- Use flats, not every subset.
- Keep rank in each exponent.
- State when qᶜ and q−1 divisions apply.
Read deeper
Matroid Theory, 2007 course notes
Federico Ardila · Free author course
Use Ardila lectures 26–29 for the Möbius and characteristic-polynomial definitions.
Open the sourceIntersection theory of matroids: variations on a theme
Federico Ardila-Mantilla · 2024 · Open exposition
Read the introduction for the reduced-coefficient convention; defer the mixed-degree theorem.
Open the sourceLecture Notes · Combinatorial Theory: Hyperplane Arrangements
MIT OpenCourseWare · Course notes · MIT OCW
Read chapter 1 notes on the intersection poset and characteristic polynomial as a second poset example.
Open the source