Hodge Theory in Combinatorics

From L to R: Karim Adiprasito, June Huh, Eric Katz

In January 2016, my colleague Josephine Yu and I are organizing a workshop called Hodge Theory in Combinatorics. The goal of the workshop is to present the recent proof of a 50-year-old conjecture of Rota by Karim Adiprasito, June Huh, and Eric Katz. In this post, I want to explain what the conjecture says and give a brief outline of its marvelous proof. I will follow rather closely this paper by Adiprasito-Huh-Katz (henceforth referred to as [AHK]) as well as these slides from a talk by June Huh.

Chromatic polynomial

If ${G}$ is a finite graph, a proper coloring of ${G}$ with ${q}$ colors is a function ${f}$ from the vertices of ${G}$ to ${\{ 1,2,\ldots,q \}}$ such that if ${v,v'}$ are adjacent then ${f(v) \neq f(v')}$ . Whitney proved in 1932 that the function ${\chi_G(q)}$ giving the number of proper colorings of ${G}$ with ${q}$ colors is a polynomial in ${q}$ , called the chromatic polynomial of ${G}$ . (The celebrated four-color theorem asserts that if ${G}$ is planar then ${\chi_G(4) > 0}$ .) Read conjectured in 1968 that for any graph ${G}$ , the coefficients of ${\chi_G(q)}$ form a log-concave sequence, i.e., $a_i^2 \geq a_{i-1} a_{i+1}$ for all ${i}$ . Read’s conjecture was proved by June Huh in a 2012 JAMS paper using methods from algebraic geometry.

A recursive algorithm for computing ${\chi_G(q)}$ makes use of the observation that ${\chi_G(q)}$ satisfies the deletion-contraction identity $\chi_G(q) = \chi_{G \backslash e} - \chi_{G / e},$ where ${G \backslash e}$ denotes ${G}$ with ${e}$ deleted and ${G / e}$ denotes ${G}$ with ${e}$ contracted. This identity also yields a simple inductive proof that ${\chi_G(q)}$ is indeed a polynomial.

Independent sets of vectors

If ${V}$ is a vector space over an arbitrary field and ${E}$ is a finite set of vectors in ${V}$ , define ${f_i}$ to be the number of independent subsets of ${E}$ of size ${i}$ . For example, if $E$ is the set of all non-zero vectors in ${\mathbf F}_2^3$ (corresponding to the Fano matroid), we have $f_0=1, f_1 = 7, f_2 = 21, f_3 = 28.$ Welsh conjectured in 1969 that ${f_i}$ is always a log-concave sequence. Welsh’s conjecture was proved by Lenz, who reduced it to the main theorem in the 2012 Mathematische Annalen paper of Huh and Katz, which itself built on the prior work of Huh.

Matroids

Gian-Carlo Rota

Gian-Carlo Rota noticed that there is a common generalization,in the context of matroids,of the chromatic polynomial of a graph and (a close cousin to) the sequence $f_i$ above. I gave an introduction to matroids in this blog post, characterizing them in terms of independent subsets and circuits. For the purposes of the present exposition, it will be convenient to present the following two alternative axiomatizations in terms of rank functions and flats.

Axiomatization in terms of rank functions

A matroid ${M}$ is a finite set ${E}$ together with a function ${r}$ from the collection ${P(E)}$ of subsets of ${E}$ to the non-negative integers, called the rank function of ${M}$ , such that:
• (R1) If ${A \in P(E)}$ then ${r(A) \leq |A|}$ .
• (R2) If ${A \in P(E)}$ and ${x \in E}$ , then ${r(A) \leq r(A \cup \{ x \}) \leq r(A) + 1}$ .
• (R3) (Submodularity axiom) If ${A,B \in P(E)}$ then ${r(A \cup B) + r(A \cap B) \leq r(A) + r(B)}$ .

Axiomatization in terms of flats

A matroid ${M}$ is a finite set ${E}$ together with a collection ${{\mathcal F}}$ of subsets of ${E}$ , called flats of ${M}$ , such that:
• (F1) ${E \in {\mathcal F}}$ .
• (F2) If ${F,F' \in {\mathcal F}}$ then ${F \cap F' \in {\mathcal F}}$ .
• (F3) (Covering axiom) If ${F \in {\mathcal F}}$ and ${x \in E \backslash F}$ , there is a unique minimal (with respect to inclusion) ${F' \in {\mathcal F}}$ containing ${F}$ with ${x \in F'}$ .

The connection with the independence axioms discussed in my earlier blog post is (briefly) as follows. The rank of a subset ${A}$ of ${E}$ is the cardinality of the largest independent subset of ${A}$ ; in particular, ${A}$ is independent if and only if ${{\rm rank}(A)=|A|}$ . A subset ${F}$ of ${E}$ is a flat of ${M}$ if and only if ${{\rm rank}(F) < {\rm rank}(F \cup \{ x \})}$ for every ${x \not\in F}$ .

The rank of ${M}$ is defined to be ${{\rm rank}(E)}$ , i.e., the rank of the largest maximal independent set in ${E}$ . The corank of a subset ${A}$ of ${E}$ is ${{\rm corank}(A) := {\rm rank}(M) - {\rm rank}(A)}$ .

Characteristic polynomial of a matroid

Generalizing the construction of the chromatic polynomial of a graph, Rota defined the characteristic polynomial of a matroid ${M}$ as
$\displaystyle \chi_M(q)= \sum_{A \subseteq E} (-1)^{|A|} q^{{\rm corank}(A)}.$

An equivalent but more useful definition is
$\displaystyle \chi_M(q)= \sum_{F \in {\mathcal F}} \mu(F) q^{{\rm corank}(F)},$
where ${\mu(F) = \mu(\emptyset,F)}$ is the Möbius function of the poset of flats of ${M}$ . (Alternatively, one can define ${\chi_M(q)}$ recursively using the deletion-contraction identity ${\chi_M(q) = \chi_{M \backslash e} - \chi_{M / e}.}$ )

Rota made the following conjecture in 1964:

Conjecture: The absolute values of the coefficients of ${\chi_M(q)}$ form a log-concave sequence.

This is the main theorem which Adiprasito, Huh, and Katz prove in their paper. It implies the conjectures of Read and Welsh mentioned above, but is significantly more general because it applies to all matroids and not just representable ones. (June Huh likes to point out that, at least heuristically, one expects that 100% of all matroids are not representable.)

The Chow ring of a matroid

We briefly outline the strategy used by Adiprasito, Huh, and Katz in their proof of Rota’s conjecture. The first step is to define a Chow ring ${A^*(M)}$ associated to an arbitrary matroid ${M}$ . The definition is due to Feichtner and Yuzvinsky, who noted that when ${M}$ is realizable over ${{\mathbf C}},$ the ring ${A^*(M)}$ coincides with the usual Chow ring of the de Concini-Procesi “wonderful compactification” ${Y_M}$ of the hyperplane arrangement complement associated to ${M}$ . Although the definition of ${A^*(M)}$ is purely combinatorial and does not require any notions from algebraic geometry, it would presumably be rather hard to motivate the following definition without knowing something about the relevant geometric background.

Let ${{\mathcal F}' = {\mathcal F} \backslash \{ \emptyset,E \}}$ be the poset of non-empty proper flats of ${M}$ . The graded ring ${A^*(M)}$ is defined as the quotient of the polynomial ring ${S_M = {\mathbf Z}[x_F]_{F \in {\mathcal F}'}}$ by the following two kinds of relations. First, one sets ${x_F x_{F'} = 0}$ whenever ${F}$ and ${F'}$ are incomparable in the poset ${{\mathcal F}'}$ . Second, one declares that for every ${a,b \in E},$ the sum of the ${x_F}$ for all ${F}$ containing ${a}$ equals the sum of the ${x_F}$ for all ${F}$ containing ${b}$ .

The generators ${x_F}$ are viewed as having degree one. If ${r=d+1}$ is the rank of ${M}$ , there is an isomorphism ${{\rm deg} : A^d(M) \rightarrow {\mathbf Z}}$ determined uniquely by the property that ${{\rm deg}(x_{F_1} x_{F_2} \cdots x_{F_d})=1}$ whenever ${F_1 \subsetneq F_2 \subsetneq \cdots \subsetneq F_d}$ is a flag in ${{\mathcal F}'}$ .

Connection to Hodge Theory

If ${M}$ is realizable, one can use the so-called “Hodge-Riemann relations” from algebraic geometry, applied to the $d$ -dimensional algebraic variety ${Y_M}$ whose complex cohomology ring is $A^*(M)_{\mathbf C} := {A^*(M) \otimes {\mathbf C}},$ to prove Rota’s log-concavity conjecture for ${M}$ . This is (in retrospect, anyway) the basic idea in the earlier paper of Huh and Katz.

We now quote from the introduction to [AHK]:

While the Chow ring of ${M}$ could be defined for arbitrary ${M}$ , it was unclear how to formulate and prove the Hodge-Riemann relations… We are nearing a difficult chasm, as there is no reason to expect a working Hodge theory beyond the case of realizable matroids. Nevertheless, there was some evidence on the existence of such a theory for arbitrary matroids.

What the authors of [AHK] do is to formulate a purely combinatorial analogue of the Hard Lefschetz Theorem and Hodge-Riemann relations and prove them for the ring $A^*(M)_{\mathbf R} := A^*(M) \otimes {\mathbf R}$ in a purely combinatorial way, making no use of algebraic geometry. The idea is that although the ring $A^*(M)_{\mathbf C}$ is (presumably) not actually the cohomology ring of a smooth projective variety, from a Hodge-theoretic point of view it behaves as if it were.

In order to formulate precisely the main theorem of [AHK], we need a combinatorial analogue of hyperplane classes, or more generally of ample and nef divisors. The connection goes through strictly submodular functions. A function ${c : P(E) \rightarrow {\mathbf R}_{\geq 0}}$ is called strictly submodular (resp. submodular) if ${c(A \cup B) + c(A \cap B) < c(A) + c(B)}$ (resp. ${c(A \cup B) + c(A \cap B) \leq c(A) + c(B)}$ ) whenever ${A,B}$ are incomparable subsets of ${E}$ . Such a function ${c}$ gives rise to an element ${\ell(c) = \sum_{F \in \mathcal{F}'} c(F) x_F \in A^1(M)_{\mathbf R}.}$ The convex cone of all ${\ell(c) \in A^1(M)}$ associated to strictly submodular (resp. submodular) classes is called the ample cone (resp. nef cone). (Actually, the ample cone in [AHK] is a priori larger than what we’ve just defined, but this is irrelevant for the purposes of the present post.)

Ample (resp. nef) classes define strictly convex (resp. convex) piecewise-linear functions on the Bergman fan ${\Delta_M}$ . I described the Bergman fan in this post in terms of the circuits of ${M}$ . However, one can also define ${\Delta_M}$ using flats; in particular, the cones of ${\Delta_M}$ correspond bijectively to flags ${F_1 \subsetneq F_2 \subsetneq \cdots \subsetneq F_d}$ of non-empty proper flats of ${M}$ , where as above ${r=d+1}$ is the rank of ${M}$ .

The main theorem of [AHK] is the following:

Theorem: Let ${M}$ be a matroid of rank ${d=r+1}$ , let ${\ell \in A^1(M)_{\mathbf R}}$ be ample, and let ${0 \leq q \leq \frac{d}{2}}$ . Then:
• (Poincaré duality) The natural multiplication map gives a perfect pairing $A^q(M) \times A^{d-q}(M) \rightarrow A^d(M) \cong {\mathbf Z}.$
• (Hard Lefschetz Theorem) Multiplication by ${\ell^{d-2q}}$ determines an isomorphism ${L_\ell^q : A^q(M)_{\mathbf R} \rightarrow A^{d-q}(M)_{\mathbf R}}$ .
• (Hodge-Riemann relations) The natural bilinear form ${Q_\ell^q : A^q(M)_{\mathbf R} \times A^q(M)_{\mathbf R} \rightarrow {\mathbf R}}$ defined by ${Q_\ell^q(a,b) = (-1)^q a \cdot L_\ell^q b}$ is positive definite on the kernel of ${\ell \cdot L_\ell^q}$ (the so-called “primitive classes”).

This is all in very close analogy with analogous results in classical Hodge theory.

To see why the theorem implies Rota’s conjecture, fix ${e \in E}$ . Let ${\alpha(e) \in S_M}$ be the sum of ${x_F}$ over all ${F}$ containing ${e}$ , and let ${\beta(e) \in S_M}$ be the sum of ${x_F}$ over all ${F}$ not containing ${e}$ . The images of ${\alpha(e)}$ and ${\beta(e)}$ in ${A^1(M)}$ do not depend on ${e}$ , and are denoted by ${\alpha}$ and ${\beta}$ , respectively.

Proposition: For all $k$ , ${{\rm deg}(\alpha^{d-k} \cdot \beta^k)}$ is equal to the ${k^{\rm th}}$ coefficient of the reduced characteristic polynomial ${\bar{\chi}_M(q) := \chi_M(q) / (q-1)}$ of ${M}$ .

Although ${\alpha}$ and ${\beta}$ are not ample, they belong to the nef cone and one may view them as a limit of ample classes. This observation, together with the Hodge-Riemann relations, allows one to deduce Rota’s conjecture in a formal way.

Strategy for proving the main theorem

The main work in [AHK] is of course establishing Poincaré duality and especially the Hard Lefschetz Theorem and Hodge-Riemann relations for ${M}$ . The actual proof is much too intricate to describe in this blog post. However, I will try to quickly give an impressionistic view of the argument.

The proof is motivated by Peter McMullen’s observation that one can deduce the g-conjecture for arbitrary simple polytopes to the case of simplicial polytopes using the “flip connectivity” of simplicial polytopes of given dimension.

The key observation in [AHK] motivated by McMullen’s work is that for any two matroids ${M}$ and ${M'}$ of the same rank on the same ground set ${E}$ , there is a diagram

where each matroidal flip preserves the validity of the Hard Lefschetz Theorem and Hodge-Riemann relations. (A subtlety is that the intermediate objects ${\Delta_i}$ are tropical varieties, i.e., balanced weighted rational polyhedral fans, but not necessarily tropical linear spaces associated to some matroid. So one leaves the world of matroids in the course of the proof, unlike with McMullen’s case of polytopes.) Using this, one reduces Rota’s conjecture to the case of the uniform matroid of rank ${r}$ on ${E}$ (whose rank function is given by ${{\rm rank}(A)={\rm min}(|A|,r)}$ for all ${A \subseteq E}$ ), in which case the conjecture can be directly verified “by hand”.

Concluding remarks

1. Every log-concave sequence ${a_0,a_1,\ldots,a_n}$ of positive real numbers is unimodal, i.e., there is a ${j}$ such that ${a_0 \leq a_1 \leq \cdots \leq a_j \geq a_{j+1} \geq \cdots \geq a_n}$ . In particular, the main theorem of [AHK] implies that the absolute values of the coefficients of the characteristic polynomial of a matroid form a unimodal sequence. See this survey paper by Stanley for many other examples of naturally occurring log-concave and unimodal sequences in combinatorics.

2. The term combinatorial geometry from the title of [AHK] is another name for a simple matroid. (A matroid is called simple if every circuit has at least 3 elements, or equivalently, if the empty set and all singleton subsets of ${E}$ are flats.) Every matroid has a canonical simplification, with the same lattice of flats $L$ , and one can recover a simple matroid uniquely from $L$ . As ${\chi_M(q)}$ can be defined purely in terms of the lattice of flats, one can immediately reduce the main theorem of [AHK] to the case of combinatorial geometries.

3. We have already mentioned that the approach given in [AHK] to proving the Hard Lefschetz Theorem and Hodge-Riemann relations was inspired in large part by the work of Peter McMullen. It is also inspired by the approach to classical Hodge Theory pioneered by de Cataldo and Migliorini.

4. The main theorem of [AHK] is related to the counterexample to Demailly’s strong version of the Hodge conjecture for positive currents given recently by Babaee and Huh. Their counterexample is based on a tropical variety that satisfies Poincaré duality and the Hard Lefschetz Theorem, but not the Hodge-Riemann relations.

5. The proof of the Lefschetz theorem for locally matroidal tropical varieties by Adiprasito and Björner uses a deformation argument similar to the one used in [AHK].

12 thoughts on “Hodge Theory in Combinatorics”

Eric says:

December 15, 2015 at 6:38 pm

First.

j.c. says:

December 16, 2015 at 9:29 am

I believe [AHK] use r+1 for the rank of the matroid, rather than r. I was confused for a while by this in your post when trying to understand how there could be a flag of length r ending in a proper flat in the definition of the degree isomorphism of the Chow ring.

- Matt Baker says:
  
  December 16, 2015 at 12:17 pm
  
  You’re right, thanks — I now write r=d+1 and have replaced r by d in several places.
  
Jim says:

January 19, 2016 at 12:15 pm

Hi Matt,

One way of expressing log-concavity is that the 2×2 minors of the Toeplitz matrix with the a_i’s down the i-th off-diagonal are non-negative. In the theory of total positivity, one asks that all the minors of such matrices are non-negative. Could it be the case that the log-concave combinatorial sequences you mention above have the property that all these minors are non-negative? Or is this known to be false?

- Karim Adiprasito says:
  
  January 19, 2016 at 1:39 pm
  
  The Hodge Riemann relations we use indeed imply such a statement, but only for rings with 2 generators. Unfortunately we do not have such a sexy statement for matroids in general.
  
- Matt Baker says:
  
  January 19, 2016 at 5:14 pm
  
  June Huh says: Jim’s condition for the infinite Toeplitz matrix says that the generating polynomial for the sequence mu has only real zeros. Apparently this fails for uniform matroids.
  
- Jim says:
  
  January 20, 2016 at 6:38 am
  
  Thanks!
  
Pingback: 月旦 I | Fight with Infinity
Pingback: Whitney Encounters of the Second Kind | Matt Baker's Math Blog
Pingback: Lorentzian Polynomials II: Applications | Matt Baker's Math Blog
Pingback: Firing games and greedoid languages | Matt Baker's Math Blog
Pingback: A Fields Medal for June Huh! | Matt Baker's Math Blog