Finding combinatorial models / statistics

Question

In many cases in combinatorics and especially algebraic combinatorics with some representation theory, the main problem is about finding the correct statistic on a mathematical object.

For example, finding the combinatorial description of symmetric functions, the invention of the inv and maj statistic to describe modified Macdonald polynomials, or the rather tricky weight on certain fillings that yield the combinatorial formula for Jack polynomials by Knop and Sahi.

Another example is the complicated charge statistic defined on permutations, words, and semi-standard Young tableaux.

A lot of hard, open problems in combinatorics boils down to finding (guessing) a combinatorial statistic, and once the correct guess is done, the rest is usually proof by induction (not always easy, but at least you know what to prove).

What techniques to people use to guess such combinatorial statistics in the first place?

This is usually not explained in the papers, only the final conjecture or proof is presented.

I am currently battling such a problem myself, and here are some techniques I have used so far:

• If the statistic is a generalization of an already existing one, see which properties might generalize. Is it linear, in some sense? Are there equalities of the form $\sigma(T) = \sigma(T')$ where $T'$ is simpler than $T$ in some sense?
• Use computer algebra to test if additional assumptions lead to a contradiction or not.
• Check if Findstat already has it in the database.
• Check natural sequences of objects against OEIS.
• Look for alternative underlying combinatorial objects, where the statistic might be more evident. For example, Young tableaux and Gelfand-Tsetlin patterns are in bijection, and some statistics are easier to define on one of these, rather than the other.

I would love to hear stories of how people guessed combinatorial statistics (or better underlying combinatorial objects) in stories like above.

Answer 1

One additional test I usually do is to check if I can extract information about its generating function given by $$\sum_{x \in \mathcal{C}_n} q^{\operatorname{stat}(x)}$$ for some decomposition $\mathcal{C} = \bigcup_{n} \mathcal{C}_n$ with $\big|\mathcal{C}_n \big| < \infty$ of your combinatoral collection.

In the best case, you find a known equidistributed statistic $\operatorname{stat'}$ to which you can possibly biject.

I guess an archetypical example would be to have the number of inversions of a permutation, so the decomposition is $Perm = \bigcup_n Perm_n$, the statistic for $n=3$ is $$ inv(123) = 0, inv(132) = 1, inv(213) = 1, inv(231) = 2, inv(312) = 2, inv(321 = 3 $$ and its generating function $f_3 = 1 + 2q + 2q^2 + q^3$. You then might realize that this is also the generating function of the major index on permutations.

Finally, let me remark: FindStat shows you the generating function (such as in http://www.findstat.org/St000018), and you can then automatically search the OEIS for the coefficients of the statistic distribution.