What is the correspondence between combinatorial problems and the location of the zeroes of polynomials called?

Question

(From MSE)

In the wikipedia article on the Italian-born American mathematician and philosopher Gian-Carlo Rota, it is stated that the one combinatorial idea he would like to be remembered for

"... is the correspondence between combinatorial problems and problems of the location of the zeroes of polynomials."

Also, a refence [1] is given for this quote. Upon reading through the interview, though, I didn't discover any more about this correspondence, nor did I find a lot by searching for it on the web.

Question 1: What is this correspondence called?

I am also interested in how these two (which seem to me) disparate problems in mathematics relate to one another, so:

Question 2: How does this correspondence work? Any references?

Finally:

3 more questions: To what extent has this correspondence been developed any further since Rota's discovery? Are there any other connections between zeroes of polynomials and combinatorics? I know algebraic geometry is concerned with the study of zeroes of polynomials, so is there any connection between (algebraic) combinatorics and algebraic geometry?

Reference:

[1] http://web.archive.org/web/20070811172343/http://www.rota.org/hotair/rotasharp.html

Answer 1

Rota himself called this correspondence "the critical problem". You can find the full quote in Michael Lugo's blog.

As explained by Garrett Birkhoff (in his book on Lattice Theory), the critical problem consists in locating the zeros of the characteristic polynomial of a geometric lattice, as defined by the Möbius function. Many extremal combinatorial problems, notably the classical problem of graph-coloring, can be re-stated as critical problems.

Combinatorial Geometries is a classic reference.

Other combinatorially defined polynomials (with further references) can be found in Lugo's blog mentioned above.

Answer 2

As Carlo Beenakker said, Rota called this the "critical problem." Rota intentionally left the statement of the critical problem slightly vague. Perhaps the closest he came to a precise formulation was in his paper with Joseph P.S. Kung and M. Ram Murty, "On the Rédei zeta function," J. Number Theory 12 (1980), 421–436. The abstract of that paper reads:

Let L be a locally finite lattice. An order function ν on L is a function defined on pairs of elements x, y (with x ≤ y) in L such that ν(x, y) = ν(x, z) ν(z, y). The Rédei zeta function of L is given by ϱ(s; L) = Σ_x∈Lμ(Ô, x) ν(Ô, x)^−s. It generalizes the following functions: the chromatic polynomial of a graph, the characteristic polynomial of a lattice, the inverse of the Dedekind zeta function of a number field, the inverse of the Weil zeta function for a variety over a finite field, Philip Hall's φ-function for a group and Rédei's zeta function for an abelian group. Moreover, the paradigmatic problem in all these areas can be stated in terms of the location of the zeroes of the Rédei zeta function.

The best way to get a feeling for what Rota was talking about is to consider some examples. The chromatic polynomial $\chi(n)$ of a graph is the number of ways to label the vertices of the graph with the numbers 1 to $n$ in such a way that adjacent vertices get distinct labels. It is not quite trivial, but also not difficult, to show that $\chi(n)$ is a polynomial function of $n$ (hence the name). Finding the chromatic number of the graph (a classical combinatorial problem, the most famous instance of which is the four-color theorem) is equivalent to finding the smallest positive integer zero of $\chi(n)$.

The chromatic polynomial may be thought of as the characteristic polynomial of the cycle matroid of the graph, so you can ask more generally about the combinatorial meaning of the zeros the characteristic polynomial of any matroid or even of any finite graded partially ordered set. In many cases these turn out to be combinatorially interesting quantities.

Furthermore, as the above paper on the Rédei zeta function shows, one can even draw a formal parallel between these polynomials and classical zeta functions. It would be cool if the zeros of the chromatic polynomial could be shown to be analogous to the zeros of the Riemann zeta function; unfortunately, they're at best analogous to the poles of the Riemann zeta function, so it's not clear that this observation buys us anything. It's an interesting thing to think about, though; maybe a nontrivial connection between combinatorics and number theory can someday be established along these lines.

Answer 3

Two keyphrases that will turn up many references in a websearch are "Combinatorial Nullstellensatz" and "the polynomial method" (or, "the polynomial method in combinatorics"). I'm not certain this is what Rota had in mind, but it certainly qualifies as a "correspondence between combinatorial problems and problems of the location of the zeroes of polynomials."

EDIT: On reading the other answers, I'm certain this is not what Rota had in mind, but it still qualifies as a "correspondence...."

Answer 4

I'm not sure why such an old question suddenly bubbled up to the (my) first page after several years, but I won't let that stop me answering it.

As explained above, Rota's critical problem is usually phrased as finding certain (integer) values where the characteristic polynomial of something (often a graph, or representable matroid) is non-zero.

But I think that describing these problems/results as "location of zeros of polynomials" is a bit disingenuous - graph colouring, like the 4-colour theorem, is essentially a combinatorial subject and the chromatic polynomial and its roots played no role in the eventual proof of the 4CT. Saying the "any planar graph is 4-colourable" is logically equivalent to "4 is not a zero of the chromatic polynomial" but I'd argue that it in this case the equivalence is superficial.

Subjects that really use the non-integer real and/or complex roots of polynomials seem to better meet the "spirit" of the question (though anyone else is free to disagree). Here the obvious candidate application is the study of the partition function of the Potts model, where statistical physicists specifically wish to compute the (limiting curves of) complex roots of these partition functions for various families of graphs. These curves provide information about phase transitions in the underlying Potts model.

The chromatic polynomial is a special limiting case of this partition function and the entire partition function is equivalent to the Tutte polynomial, so these connections somehow seem more fundamental.