Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

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. For an infeasible polynomial system, the (complex) Hilbert Nullstellensatz gives a certificate that the associated combinatorial problem is infeasible. Thus, unless $\text{P}=\text{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).