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.

  • 5
    Knowing that it has to be invariant under certain symmetries definitely can help. – Sam Hopkins Aug 27 '15 at 14:48

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.

  • That is a good suggestion, do you have any hints what to do when you only know the generating function for some subsets, (but dont know which exact value goes to which object)? – Per Alexandersson Aug 30 '15 at 19:35
  • I think you can add an example in your answer. But it is a good answer already. – Henry.L Aug 31 '15 at 0:52
  • @PerAlexandersson, can you extract what you might be able to do from the above example? Otherwise, you must be a little more specific on the data you have (e.g. if you do not know which value goes where, is it at least in the same graded component so that it does not matter for the generating function?). – Christian Stump Aug 31 '15 at 6:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.