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 3colorable,
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 edgechromatic
number, or the largest kcolorable 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 nonlinear
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 minimumdegree 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 3colorability, 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).
