Follow a counting problem all the way to the theorem’s input.
Prerequisites: 17 · Graph coloring becomes a polynomial, 18 · The lattice and characteristic polynomial, 19 · Log-concavity: why a sequence forms a hill, 23 · Build one actual Chow ring, 24 · The Hodge bridge: signature → inequality
Draw C₄ and remove one edge to form a path. Before computing, predict which changes in rank, spanning-tree bases and color counts. A count for one graph is evidence about that graph; the general inequality needs a theorem.
The graphic matroid has the graph edges as its ground set. For a graph with c components, P_G(q)=qᶜχ_M(q). For a nonempty loopless matroid, χ̄_M(q)=χ_M(q)/(q−1). A rank r+1 matroid has reduced degree r and Chow top degree r.
Choose the first vertex in q ways and the second in q−1 ways. If the third equals the first, the fourth has q−1 choices; otherwise the third and fourth each have q−2 choices. Thus q(q−1)[(q−1)+(q−2)²]=q⁴−4q³+6q²−3q. Dividing by q gives χ=q³−4q²+6q−3=(q−1)(q²−3q+3). The rank is 3 and four edge deletions give four spanning-tree bases.
For a finite loopless matroid of rank r+1, the mixed-degree identity μᵏ=deg(αr−kβᵏ) and the Hodge–Riemann relations imply weak log-concavity of its absolute reduced characteristic coefficients. This general input is due to Adiprasito–Huh–Katz; the four-cycle arithmetic above is an illustration, not its proof.
At q=3, P=18. The absolute reduced coefficients are (1,3,3); the gap is 3²−1×3=6. Delete an edge: the tree has P=q(q−1)³, χ̄=(q−1)² and coefficients (1,2,1), gap 3. This tree’s free matroid U₃,₃ is the earlier computed Chow toy case, not C₄’s ring.
| Proof-map arrow | Reason | For C₄ |
|---|---|---|
| Graph → P | Count proper vertex colorings | q(q−1)[(q−1)+(q−2)²] |
| P → χ → χ̄ | Connected graph; nonempty loopless matroid | Divide by q, then q−1 |
| χ̄ → μᵏ | Read absolute alternating coefficients | (1,3,3), gap 6 |
| μᵏ → mixed degree | General coefficient identity, AHK Proposition 9.5 | Do not infer from two graphs |
| Signature → inequality | Hodge–Riemann input, AHK Theorem 1.4 and Proposition 9.8 | General guarantee, not this arithmetic test |
Counterexample to the proof shortcut: checking C₄ and its tree proves only their own gaps. It cannot establish log-concavity for arbitrary, possibly nonrepresentable matroids. The deep coefficient identity and Hodge–Riemann statement are invoked, not proved by two computations.
Use the graph lab’s cycle and path presets, then make the proof-map table before looking at the numerical anchors. Predict rank 3 for both, bases 4 versus 1, and the changed reduced coefficients.
What changes, and what remains invariant, when you remove exactly one edge?
How many spanning-tree bases does a simple six-cycle C₆ have?
For the seven-vertex path, the reduced coefficients are those of (q−1)⁵. What is the first interior log-concavity gap?
In the teach-back field, submit a six-arrow proof map from C₄ to P, χ, χ̄, mixed degrees and the Hodge inequality. Label each calculation you performed and each theorem you invoked. Include the deleted-edge comparison.
Gary Gordon & Jennifer McNulty · Publisher contents
Use the publisher contents to locate §9.6, pp.340–348 on chromatic polynomials; return to lesson 24 for the AHK paper and its numbered theorem inputs.
Open the sourceMIT OpenCourseWare · Course lecture · MIT OCW
Lecture 6 gives proper coloring as a prerequisite; it does not establish the matroid polynomial or Hodge arrows.
Open the source