6

Recently there has been tremendous progress in showing that certain sequences of numbers $(a_0,a_1,\ldots,a_n)$ attached to a combinatorial object (such as the coefficients of the characteristic polynomial of a matroid, or the number of size $i$ independent sets of a matroid) are unimodal.

Sometimes the question arises: why care?

One very reasonable answer is that the techniques developed to tackle these problems (combinatorial abstractions of methods from algebraic geometry) justify them.

But another answer I might give is that they are a first step towards exact classification results.

The gold standard I am aware of when it comes to exact classifications of this sort is the g-theorem for simplicial polytopes, which says that a vector $(f_0,\ldots,f_d)$ is an $f$-vector a simplicial $d$-polytope if and only if:

  • we have $h_i = h_{d-i}$ for all $i=0,\ldots,\lfloor d/2 \rfloor$ (Dehn-Sommerville equations), where the $h$-vector is defined from the $f$-vector by the g.f. equation $h(t)=f(t-1)$;
  • we have $g_i \geq0$ for the $g$-vector, defined by $g_i := h_i-h_{i-1}$ for $i=0,\ldots,\lfloor d/2 \rfloor$;
  • the $g$-vector is a so-called "Macaulay vector".

Being a Macaulay vector is equivalent to being the rank generating function for an order ideal of monomials and it also has a purely numerical description; see e.g. Eur's A brief note on McMullen’s g-conjecture.

But it is really the 2nd condition here I want to focus on, because (together with the Dehn-Sommerville symmetry) it is the same as saying that the $h$-vector is unimodal. So we see unimodality is a step towards classification: actually symmetry and unimodality give all linear equalities and inequalities satisfied by the $h$-vector.

Question: Can you give other examples of known or conjectured classifications of numerical sequences from combinatorics like this? Especially where unimodality enters into play, but even if not.

E.g. is there any idea of when a sequence of numbers is the coefficients of the chromatic polynomial of a graph?

Sam Hopkins
  • 22,785
  • Some related questions of mine: https://mathoverflow.net/questions/255757/why-do-combinatorial-abstractions-of-geometric-objects-behave-so-well and https://mathoverflow.net/questions/391670/log-concavity-of-matroids-characterization-of-equality. – Sam Hopkins Jun 02 '22 at 22:03
  • 1
    Perhaps not combinatorics, but Shephard showed (https://londmathsoc.onlinelibrary.wiley.com/doi/epdf/10.1112/S0025579300001674) that the Aleksandrov-Fenchel inequalities, i.e., $V_i^2\geq V_{i-1}V_{i+1}$, for the mixed volumes $V_i$ of two convex bodies are sufficient conditions on the $V_i$'s. – Richard Stanley Jun 03 '22 at 23:39
  • 1
    Presumably you're aware of this already, but maybe it's worth stating anyway: the Kruskal–Katona theorem characterizing $f$-vectors of abstract simplicial complexes and Macaulay's theorem characterizing the $h$-vectors of multicomplexes, both of which are special cases of a theorem of Clements and Lindström, A generalization of a combinatorial theorem of Macaulay, J. Combin. Theory 7 (1969), 230–238. – Timothy Chow Jun 04 '22 at 14:53
  • Thanks, those all are very nice examples of the kind of thing I had in mind! – Sam Hopkins Jun 04 '22 at 18:46

0 Answers0