Systems of polynomial equations over the complex or real numbers can be used to model combinatorial problems. In this way, a problem is feasible (e.g. a graph is 3-colorable, Hamiltonian, etc.) if and only if a certain system of equations has a solution. In the first part of this talk I explain new polynomial encodings for the problems of finding in a graph its longest cycle, the largest planar subgraph, the edge-chromatic number, or the largest k-colorable subgraph.

In the second part of the talk I will explain why these encodings are quite interesting. Briefly work of M. Laurent, J. Lasserre and P. Parrilo implies that when an optimization problem is modeled by a zero dimensional radical ideal it has a finite sequence of semidefinite programs that converge to the optimal solution. This is the case even for non-linear objective functions. A special case is that of feasibility questions, then we see that the problem can be approximated by a sequence of linear algebra problems. This follows from Hilbert's Nullstellensatz.

For an infeasible polynomial system, the (complex) Hilbert Nullstellensatz gives a certificate that the associated combinatorial problem is infeasible. Thus, unless P=NP, there must exist an infinite sequence of infeasible instances of each hard combinatorial problem for which the minimal degree of a Hilbert Nullstellensatz certificate of the associated polynomial system grows.

We show that the minimum-degree of a Hilbert Nullstellensatz certifying that there is no stable set of size larger than the stability number of the graph is the stability number of the graph. Moreover, such a certificate contains at least one term per stable set in G. In contrast, for 3-colorability, we found only families with Nullstellensatz of degree four.

This is joint work with S. Margulies (UC Davis) J. Lee (IBM Research), and S. Onn (Technion Haifa).