How to use Hilbert series to count combinatorial objects?

Question

In THE SLOPES DETERMINED BY n POINTS IN THE PLANE by JEREMY L. MARTIN, Page 2, Theorem 1.1, a Hilbert series is used to compute some combinatorial objects:

Let $R_n=k[m_{1,2}, \ldots, m_{n-1,n}]$, and let $I_n$ be the ideal generated by the tree polynomials of all rigidity circuits in the complete graph $K_n$. Then the coefficient $h(n,k)$ of the numerator of the Hilbert series of $R_n/I_n$ counts the number of perfect matchings on $[1, 2n − 4]$ with exactly $k$ long pairs, that is, pairs not of the form $\{i,i + 1\}$.

In general, if we want to compute some combinatorial objects using Hilbert series, how to define the ring $R_n$ and the ideal $I_n$?

Are there some other examples which count some combinatorial objects using Hilbert series?

Thank you very much.

Answer 1

For a simplicial complex $\Delta$, the numerator of the Hilbert series of the Stanley-Reisner ring $k[\Delta]$ is precisely the $h$-polynomial of the simplicial complex. (Recall that the $h$-polynomial is, modulo proper indexing, obtained from the $f$-polynomial by plugging in $x-1$. The $f$-polynomial is the polynomial whose coefficients record the number of faces of $\Delta$ of each dimension.)

Often for nice simplicial complexes these $h$-polynomial coefficients have a combinatorial meaning. For instance, if $\Delta$ is the dual polytope to the regular (Type A) permutohedron, then the $h$-polynomial coefficients are the famous Eulerian numbers, which count permutations by descents: see https://oeis.org/A008292.

I don't think this is an instance where a Hilbert series "helps you count a class of combinatorial objects" per se, but it is a representative example of how the numerators of Hilbert series arise in algebraic combinatorics. In particular, I think the philosophy is that $h$-polynomials tend to behave like Eulerian polynomials; see for example the behavior for generalized permutohedra as worked out by Postnikov-Reiner-Williams (https://arxiv.org/abs/math/0609184) or check out the recent textbook by Petersen (https://www.springer.com/us/book/9781493930906).

Note that plugging in $1$ to the $h$-polynomial should give you the number of facets of $\Delta$, so if the coefficients of this polynomial are all nonnegative integers you should think that the coefficients count facets by some statistic (in the permutohedron case we get permutations <-> vertices of permutohedron <-> facets of the dual polytope, and the relevant statistic for permutations is descents). As Martin explains in his paper, in the case where $\Delta$ is shellable, there is always a choice of this statistic coming from a given shelling.

Answer 2

See:

Mordechai Katzman, Counting monomials

This paper presents two enumeration techniques based on Hilbert functions. The paper illustrates these techniques by solving two chessboard problems.

Answer 3

Well, the Hilbert series is just a special case of the Frobenius map of an $S_n$-action on a (graded) vector space. Thus, any time you have a combinatorial statement about Schur positivity (thus arising from some representation of an $S_n$-module), where the coefficients are of combinatorial nature, you also have a Hilbert-series with a combinatorial interpretation.

Take for example, the graded vector space $C[x_1,\dotsc,x_n]$, that comes with a natural $S_n$ action (permuting variables). Then the (graded) Frobenius series is just $F=\sum_{\lambda \vdash n} s_{\lambda}(1,q,q^2,\dotsc)s_\lambda$ and the Hilbert series is $(1-q)^{-n}$, which can be obtained by taking the inner product $\langle F, h_{1^n} \rangle$ (the Hall inner product).

There are more examples in Jim Haglund's book, related to diagonal harmonics.

For example, the Stanley symmetric functions are Schur positive, and the expansion is given by the Edelman-Green correspondence. At the same time, these are the Frobenius image of certain generalized Specht modules, so you can then quite easily give a combinatorial interpretation of the Hilbert series.