### Rota on Combinatorics

#### Posted by David Corfield

From an interview with Gian-Carlo Rota and David Sharp:

Combinatorics is an honest subject. No adèles, no sigma-algebras. You count balls in a box, and you either have the right number or you haven’t. You get the feeling that the result you have discovered is forever, because it’s concrete. Other branches of mathematics are not so clear-cut. Functional analysis of infinite-dimensional spaces is never fully convincing; you don’t get a feeling of having done an honest day’s work. Don’t get the wrong idea - combinatorics is not just putting balls into boxes. Counting finite sets can be a highbrow undertaking, with sophisticated techniques.

I remember somewhere else he spoke of his mathematical ‘bottom line’ as concerned with putting balls in boxes.

Much combinatorics of our day came out of an extraordinary coincidence. Disparate problems in combinatorics, ranging from problems in statistical mechanics to the problem of coloring a map, seem to bear no common features. However, they do have at least one common feature: their solution can be reduced to the problem of finding the roots of some polynomial or analytic function. The minimum number of colors required to properly color a map is given by the roots of a polynomial, called the chromatic polynomial; its value at $N$ tells you in how many ways you can color the map with $N$ colors. Similarly, the singularities of some complicated analytic function tell you the temperature at which a phase transition occurs in matter. The great insight, which is a long way from being understood, was to realize that the roots of the polynomials and analytic functions arising in a lot of combinatorial problems are the Betti numbers of certain surfaces related to the problem. Roughly speaking, the Betti numbers of a surface describe the number of different ways you can go around it. We are now trying to understand how this extraordinary coincidence comes about. If we do, we will have found a notable unification in mathematics.

Does anyone know whether progress has been made in explaining the ‘extraordinary coincidence’?

Posted at April 2, 2007 2:43 PM UTC
## Re: Rota on Combinatorics

The minimum number of colors required to properly color a map is given by the roots of a polynomial, called the chromatic polynomial; its value at N tells you in how many ways you can color the map with N colors.Perhaps I’m only showing my naivete, but I’m not sure what the roots have to do with anything. As he says only a moment later, the natural interest is in the values at natural numbers. There are a lot of polynomials that it has never occurred to me to seek the roots of – Kazhdan-Lusztig polynomials, for example.

The idea that polynomials with positive coefficients (as combinatorial ones usually have, of course) should be Poincare polynomials of some space has made great advances. My favorite example is the Geometric Satake Correspondence, in which the weight multiplicities in a G-representation (w.r.t. the circle in a principal SL_2) are shown to be the coefficients of the intersection homology Poincare polynomial of a Schubert variety in the loop Grassmannian of the Langlands dual of G.

If a polynomial arises as the q-analogue of some number, then the evidence is especially compelling that there should be a space whose F_q-points are being counted, and the Weil conjectures say that one could equivalently (to some extent) compute the Poincare polynomial of that space.