Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

April 2, 2007

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 NN tells you in how many ways you can color the map with NN 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

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1224

10 Comments & 1 Trackback

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.

Posted by: Allen Knutson on April 2, 2007 5:15 PM | Permalink | Reply to this

Re: Rota on Combinatorics

Allen wrote:

Rota wrote:

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.

Probably Rota just meant that there are no ways to N-color a map (or really a graph) if its chromatic polynomial vanishes at N. Using this, we can in principle figure out the minimum number of colors required.

Rota was probably talking this way just to be comprehensible by layfolk while still sounding really cool.

But, there are weirdly interesting questions about the non-integral roots of the chromatic polynomial! From week22:

Consider the problem of trying to color the vertices of a graph with nn colors in such a way that no two vertices at opposite ends of any given edge have the same color. Let P(n)P(n) denote the number of such n-colorings. This turns out to be a polynomial in nn - it’s not hard to see using recursion relations similar to the skein relations above. It also turns out that the 4-color theorem is equivalent to saying that the vertices of any planar graph can be 4-colored. (To see this, just use the idea of the “dual graph” of a graph - the vertices of the one being in 1-1 correspondence with the edges of the other.) So, another way to state the 4-color theorem is that for no planar graph does the polynomial P(n)P(n) have a root at n=4n = 4.

P(n)P(n) is called the “chromatic polynomial” and has been intensively investigated. One very curious thing is this. Remember the golden mean

Φ=(5+1)/2=1.61803398874989484820458683437...? \Phi = (\sqrt{5}+ 1)/2 = 1.61803398874989484820458683437...?

Well, Φ+1\Phi + 1 is never a root of the chromatic polynomial of a graph! (Unless the polynomial vanishes identically, which happens just when the graph has loops.) The proof is not all that hard, and it’s in Saaty and Kainen’s book.

However — and here’s where things get really interesting — in 1965, Hall, Siry and Vanderslice figured out the chromatic polynomial of a truncated icosahedron. (This looks like a soccer ball or buckyball.) They found that of the four real roots that weren’t integers, one agreed with Φ+1\Phi + 1 up to 8 decimal places! Of course, here one might think the 5-fold symmetry of the situation was secretly playing a role. But in 1966 Barri tabulated a bunch of chromatic polynomials in her thesis, and in 1969 Berman and Tutte noticed that most of them had a root that agreed with Φ+1\Phi + 1 up to at least 5 decimal places.

This curious situation was at least partially explained by Tutte in 1970. He showed that for a triangular planar graph (that is, one all of whose faces are triangles) with nn vertices one has

|P(Φ+1)|Φ 5n |P(\Phi + 1)| \le \Phi^{5-n}

This is apparently not a complete explanation, though, because the truncated icosahedron is not triangular.

This is not an isolated freak curiosity, either! In 1974 Beraha suggested checking out the behavior of chromatic polynomials at what are now called the “Beraha numbers”

B(n)=4cos 2(π/n). B(n) = 4 cos^2(\pi/n).

Note by the way that B(n)B(n) approaces 4 as nn approaches infinity. It turns out that the roots of chromatic polynomials seem to cluster near Beraha numbers — as if graphs were trying to come really close to being impossible to 4-color!

For example, the four nonintegral real roots of the chromatic polynomial of the truncated icosahedron are awfully close to B(5),B(7),B(8)B(5), B(7), B(8) and B(9)B(9). Beraha made the following conjecture: let P iP_i be a sequence of chromatic polynomials of graphs such whose number of vertices approaches infinity as ii \to \infty. Suppose r ir_i is a real root of P iP_i and suppose the r ir_i approach some number xx. Then xx is a Beraha number. In work in the late 60’s and early 70’s, Tutte proved some results showing that there really was a deep connection between chromatic polynomials and the Beraha numbers.

Well, to make a long story short (I’m getting tired), the Beraha numbers also have a lot to do with the quantum group SU(2)SU(2). This actually goes back to some important work of Jones right before he discovered the first of the quantum group knot polynomials, the Jones polynomial. He found that — pardon the jargon burst — the Markov trace on the Temperley-Lieb algebra is only nonnegative when the Markov parameter is the reciprocal of a Beraha number or less than 1/4. When the relationship of all this stuff to quantum groups became clear, people realized that this was due to the special nature of quantum groups when qq is an nnth root of unity (this winds up corresponding to the Beraha number B(n)B(n).) This all leads up to a paper that, unfortunately, I have not yet read:

  • Zeroes of chromatic polynomials: a new approach to the Beraha conjecture using quantum groups, by H. Saleur, Comm. Math. Phys. 132 (1990) 657.

This apparently gives a “physicist’s proof” of the Beraha conjecture, and makes use of conformal field theory, that is, quantum field theory in 2 dimensions that is invariant under conformal transformations.

This all sounds quite cool, and I wish I knew what became of these ideas later on…

However, while Xiao-Song Lin found fascinating patterns in the roots of the Jones polynomials of random links, Dan Christensen and Igor Khavkine’s work suggests that some of these patterns may simply be due to the polynomials having integer coefficients!

The chromatic polynomial also has integer coefficients. So, maybe some of the Beraha conjecture could be explained simply by that fact??? I have no idea.

Posted by: John Baez on April 3, 2007 12:35 AM | Permalink | Reply to this

Re: Rota on Combinatorics

The chromatic polynomial with q colors is nothing but the partition function of the antiferromagnetic q-state Potts model at T = 0; this forces adjacent spins/colors to be different. At non-zero temperature the partition function becomes the dichromatic polynomial, which depends on two variables q and T. At the critical temperature Tc, it is described by a CFT. If the number of colors is given by

q = 4 cos2(π/m+1)

the CFT at criticality has central charge

c = 1 - 6/m(m+1),

with the same value of m. I.e., the Beraha numbers correspond to the discrete unitary series on the CFT side. In particular, the Ising model corresponds to m = 3.

I always found it remarkable that zeroes of the partition function at T = 0 correspond to unitarity at criticality. But of course, this stuff has a severe limitation: it only works in 2D.

Posted by: Thomas Larsson on April 4, 2007 11:24 AM | Permalink | Reply to this

Re: Rota on Combinatorics

Also note that when m -> infinity, c -> 1 and q -> 4. This has something to do with the four-color theorem.

Posted by: Thomas Larsson on April 4, 2007 11:26 AM | Permalink | Reply to this

Re: Rota on Combinatorics

Is this what John was talking about when discussing Bar-Natan’s paper on the 4 color theorem at the end of TWF96?

Posted by: David Corfield on April 4, 2007 4:34 PM | Permalink | Reply to this

Re: Rota on Combinatorics

I don’t know about that. It is, however, exactly what I was talking about above in the quote from week22. As mm \to \infty, the Beraha number q=4cos 2(π/m+1)q = 4 \cos^2 (\pi/m+1) approaches 4, and we should get some information about the 4-color theorem.

Posted by: John Baez on April 11, 2007 2:47 AM | Permalink | Reply to this

Re: Rota on Combinatorics

Rota wrote:

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.

Rota is engaged in some clever salesmanship here, and demonstrating how he could never resist a rhetorical flourish, even if it required a little inconsistency in his stance.

Here he’s suggesting that it takes balls to do combinatorics — that it’s a concrete, manly sort of activity. No fancy “adèles” with their French accents here! But in other pieces, and in his own work, he emphasized the power of abstraction in combinatorics, like the use of Hopf algebras, and espèces de structure.

Indeed, later here he writes:

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.

So, he’s actually claiming both ends of the spectrum for combinatorics: the concrete and the abstract.

But this is not unique to combinatorics. To find all the integer solutions of a polynomial equation sounds quite concrete — but before you know it, you wind up using things like adèles.

Posted by: John Baez on April 3, 2007 1:15 AM | Permalink | Reply to this

Re: Rota on Combinatorics

One of my pet peeves is when people say that the pp-adic numbers are merely formal devices but that the real numbers are, well, real. So, it’s nice to see Rota label the adeles as formal. If he had only meant the pp-adic part was formal and not the real part, he surely wouldn’t have bothered to mention the adeles!

Posted by: James on April 3, 2007 1:58 PM | Permalink | Reply to this
Read the post Toegepaste wiskunde volgens Rota en Sharp
Weblog: Filosofie voor elke dag
Excerpt: David Corfields blog wees me gisteren op een interessant interview met de wiskundigen Gian-Carlo Rota en David Sharp. Het dateert al uit 1985, maar bevat heel wat boeiende inzichten over wiskunde, filosofie en kunstmatige intelligentie. Zo heet het artike
Tracked: April 3, 2007 5:36 PM

Re: Rota on Combinatorics

He’s certainly not averse to abstract constructions:

“What can you prove with exterior algebra that you cannot prove without it?” Whenever you hear this question raised about some new piece of mathematics, be assured that you are likely to be in the presence of something important. In my time, I have heard it repeated for random variables, Laurent Schwartz’ theory of distributions, ideles and Grothendieck’s schemes, to mention only a few. A proper retort might be: “You are right. There is nothing in yesterday’s mathematics that could not also be proved without it. Exterior algebra is not meant to prove old facts, it is meant to disclose a new world. Disclosing new worlds is as worthwhile a mathematical enterprise as proving old conjectures.” (Indiscrete Thoughts, 48)

And, as Founding Editor of Advances in Mathematics, we have Rota to thank for the publication of:

A. Joyal, Une théorie combinatoire des séries formelles, Advances in Mathematics 42, (1981) 1-82.

A. Joyal and R. Street, Braided tensor categories, Advances in Mathematics 102 (1993), no. 1, 20-78.

J. Baez and J. Dolan, Higher-dimensional algebra III: nn-categories and the algebra of opetopes, Advances in Mathematics 135 (1998), 145-206.

Posted by: David Corfield on April 3, 2007 5:49 PM | Permalink | Reply to this

Re: Rota on Combinatorics

Okay, now about that ‘extraordinary coincidence’…

(Maybe I missed something.)

Posted by: Chris W. on April 11, 2007 2:18 AM | Permalink | Reply to this

Post a New Comment