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

(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:

-
Crossposted on math.SE: math.stackexchange.com/questions/363522/… –  Qiaochu Yuan Apr 16 '13 at 18:38
@Qiaochu Yuan: Jup. You can also find the question by clicking on the "MSE" hyperlink at the top of the question. –  Max Muller Apr 16 '13 at 18:41

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.

-

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 s=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."

-

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.

-
Many thanks! It seems you have written about this subject as well: www-math.mit.edu/~tchow/sieves.pdf . –  Max Muller Apr 17 '13 at 20:17