Hodge theory in combinatorics
Matthew Baker · 2017 survey · Open research survey
Read §4.4 for the Hodge route to log-concavity; return to the introduction for the graph coefficient question.
Open the sourceLog-concavity: why a sequence forms a hill
A multiplicative inequality becomes a slope condition.
Prerequisites: 02 · Why enlarge the number system?, 05 · From seeing a pattern to proving it, 18 · The lattice and characteristic polynomial
Understand
Objectives
- Compute every local gap before describing the shape.
- Derive the ratio criterion only for positive terms.
- Explain why no internal zeros is needed for the unimodality implication.
Start with something you can see
Type 1, 2, 5, 2, 1 into the sequence lab. Predict whether its single peak guarantees log-concavity; then compare with 1, 0, 0, 1. The lab accepts both as text, even though its preset hill uses a different sequence. Record the inequality at each interior position before looking at the result.
Give the idea a precise name
A finite sequence of nonnegative terms is log-concave when each interior term squared is at least the product of its neighbors. This is a weak inequality: equality is permitted. A sequence is unimodal if it never increases again after it starts decreasing. An internal zero lies between two positive terms.
aₖ² ≥ aₖ₋₁aₖ₊₁
For positive terms, divide by aₖaₖ₋₁ to obtain aₖ/aₖ₋₁ ≥ aₖ₊₁/aₖ. Consecutive growth ratios cannot increase. Once one ratio falls below one, later ratios cannot exceed one. For nonnegative terms the same conclusion needs no internal zeros: the positive terms then form one interval, with zeros only at its ends. Never divide by a zero term or take its logarithm.
Work one small world
For the reduced characteristic coefficients (1,3,3) from the four-cycle, the only gap is 3²−1×3=6. Here is a separate pair of tests:
| Sequence | Interior gaps aₖ²−aₖ₋₁aₖ₊₁ | Conclusion |
|---|---|---|
| (1,2,5,2,1) | −1, 21, −1 | one peak; not log-concave |
| (1,0,0,1) | 0, 0 | weakly log-concave; not unimodal |
Counterexample to “every hill is log-concave”: (1,2,5,2,1) rises and falls once, but 2²<1×5 at both shoulders. Counterexample to omitting the support condition: (1,0,0,1) satisfies both local inequalities while falling and then rising.
THE BRIDGEThe next lesson gives a normalized geometric coefficient sequence whose inequality can be calculated directly.
WHERE THIS IDEA STOPSAn arbitrary unimodal sequence need not be log-concave, and a picture of a hill is not a proof.
Experiment
Use the text input, not the preset, for (1,2,5,2,1); compare the lab’s hill and zero-trap presets. The logarithm checkbox is unsuitable for zero terms.
What does aₖ²≥aₖ₋₁aₖ₊₁ say about two successive growth ratios?
Check & explain
Which claim is valid?
- Every one-peaked sequence is log-concave
- A nonnegative log-concave sequence with no internal zeros is unimodal
- Weak log-concavity requires every inequality to be strict
What is the gap a₁²−a₀a₂ for (2,5,4)?
Teach back
Explain the ratio argument on a positive sequence, then use both table rows to show exactly which converse or omitted hypothesis fails.
- Divide only by positive terms.
- Name the failed 4≥5 test.
- Distinguish the internal-zero case from a failure of log-concavity.
Read deeper
Hodge Theory for Combinatorial Geometries
Karim Adiprasito, June Huh & Eric Katz · Primary research
Read the introductory log-concavity statements and their positivity qualification.
Open the sourceThe log-concavity conjecture and the tropical Laplacian
June Huh · Institute for Advanced Study · Lecture · 110 min
Optional: watch the full advanced talk after solving both sequence tests; no particular passage is needed for this lesson.
Open the source