Please note, this post is based on a preprint and the original paper has not yet been published after peer review.
Some of the hardest questions to answer in math are the simplest to state. For example “when does a sequence of numbers $a_1, a_2, a_3, \ldots$ have the property that $a_{i}^2 \geq a_{i-1}a_{i+1}?” A sequence having this property is called “log-concave”. To get familiar with log-concavity, let’s consider the most famous log-concave sequence: the sequence found by specifying a row of Pascal’s triangle:
For example, in the last row we see that $36 \geq 15$ and $15^2 = 225 > 120 = 20\cdot 6$.
If you are handed any finite sequence, you can check whether or not it is log-concave. A much deeper question is to determine whether or not the process that gave rise to the sequence will always produce a log-concave sequence. For example, are the rows listed in the figure above the only log-concave rows of Pascals triangle? (No.) Or, will any row be? (Yes.) Amazingly, one successful technique has been to utilize geometry to prove that certain processes give log-concave sequences. A 2022 Fields Medal was awarded to June Huh for pioneering this approach.
Huh, together with postdoctoral scholar Christopher Eur and graduate student Matt Larson, recently released Stellahedral Geometry of Matroids as a preprint. (This means the paper has not yet been peer reviewed, but nearly every math paper is posted to the arXiv as a preprint before being submitted to a journal and subjected to the peer review process.) Eur, Huh, and Larson show, among other results, that a polynomial coming from the “Tutte polynomial” has log-concave coefficients, answering a question David Wagner asked in 1998.
The Tutte polynomial is a polynomial associated with a matroid. Given a matroid, one can compute its Tutte polynomial. But what even is a matroid? There are many different definitions of a matroid. One of the ways to define a matroid on $n$ elements (called the “groundset”) is by specifying a polytope, a convex subset of the hypercube $[0,1]^n \subseteq R^n$, whose vertices have coordinates either $1$ or $0$, and each edge is parallel to the vector $e_i – e_j$ for some $1 \leq I, j \leq n$. The coordinates of the vertices tell you what ground set elements are associated with that vertex.
For example, if $\langle 0,1,1,0 \rangle$ is a vertex of the matroid polytope on the groundset $\{a,b,c,d\}$, then one of the basis is $\{b,c\}$. The collection of the vertices of one of these special polytopes is called the set of bases of the matroid. The rank of a vertex (more commonly called a basis) is defined to be the sum of the coordinates, so in our example above $\{b, c\}$ has rank two. Because of the condition that each edge is parallel to $e_i – e_j$, all vertices have the same rank, which we call the rank $r(M)$ of the matroid. Starting with this data, one can define the rank $r(S)$ of any subset $S$ of the groundset, which will be an integer between $0$ and $r(M)$.
Once we have fixed a matroid $M$, we can define the Tutte polynomial $T_M$:
\[ T_M(x,y) = \sum_{S \subseteq E} (x-1)^{r(M) – r(S)} (y-1)^{|S|-r(S)} \]
Many important numbers and polynomials are evaluations of $T_M(x,y)$. A number or polynomial is said to be an “evaluation” of $T_M(x,y)$ if there is some way to plug-in a combination of variables and values to $T_M(x,y)$ to obtain that number or polynomial. The most famous evaluation of the Tutte polynomial is the characteristic polynomial
\[ \chi(t)=(-1)^r(m)T_M(1-t,0) \]
which generalizes the chromatic polynomial of a graph. A famous conjecture of Andrew Heron, Gian-Carlo Rota, and Dominic Welsh posed that the coefficients of $\chi(t)$ form a log-concave sequence. Karim Adiprasito, Huh, and Eric Katz proved the conjecture in 2018. (Here are some notes on the proof.) In Stellahedral Geometry of Matroids, Eur, Huh, and Larson show that the evaluation \[q^r(M) T_M(q^{-1}, q+1)\] also gives a log-concave sequence.
The proof relies on understanding a family of polytopes called stellahedra. In order to build a stellahedron, one first builds the permutohedron. The vertices of the $n-1$-dimensional permutohedron are all the points whose coordinates are rearrangements of coordinates $(1,2,3,\ldots, n).$ For example, the $2$-dimensional permutohedron is shown below:
The stellahedron consists of all the points $u$ with all positive coordinates such that there is a point $v$ in the permutohedron with $v – u$ still having positive coordinates. The stellahedron in three-dimensions is shown below:
The hexagonal face is exactly the permutohedron. The other faces arise as a result of the subtraction condition. Informally, you can think of them as points that are “closer” to the origin than the permutohedron.
To show that $q^r T_M(q^{-1}, 1+q)$ is log-concave, the authors use the stellahedron, together with tools from algebraic geometry, to show that a more general polynomial (which is itself an evaluation of the Tutte polynomial) is Lorentzian. (See this video series for more on Lorentzian polynomials.) Lorentzian polynomials are a general class of polynomials which tend to have nice log-concavity properties. More concretely, the authors show that the polynomial \[t_M(x,y,z,w) = (x+y)^{-1}(y+z)^{r}(x+w)^{n-r} T_M(\frac{x+y}{y+z}, \frac{x+y}{x+w})\] is a (normalized) Lorentizian polynomial. Then the result that $q^r T_M(q^{-1}, 1+q)$ is log-concave follows from evaluating $t_M(1,0,q,0)$.
June Huh and his coauthors have shown the world that by studying the geometry of different polytopes, one can prove that the process of generating the polynomial $q^r T_M(q^{-1}, 1+q)$ will always give a log-concave sequence. This paper is yet another example of the power of this technique that continues to chip away at the hardest problems in math.