# Susan Margulies: Hilbert's Nullstellensatz and Linear Algebra: An Algorithm for Determining Combinatorial Infeasibility

Source: Discrete mathematics seminar

**Povzetek. **
Unlike systems of linear equations, systems of multivariate
polynomial equations over the complex numbers or finite fields can
be compactly 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 given system of polynomial equations has a
solution. Via Hilbert's Nullstellensatz, we generate a sequence of
large-scale, sparse linear algebra computations from these
non-linear models to describe an algorithm for solving the
underlying combinatorial problem. As a byproduct of this algorithm,
we produce algebraic certificates of the non-existence of a solution
(i.e., non-3-colorability, non-Hamiltonicity, or non-existence of an
independent set of size *k*).

In this talk, we present theoretical and experimental results on the size of these sequences, and the complexity of the Hilbert's Nullstellensatz algebraic certificates. For non-3-colorability over a finite field, we utilize this method to successfully solve graph problem instances having thousands of nodes and tens of thousands of edges. We also describe methods of optimizing this method, such as finding alternative forms of the Nullstellensatz, adding carefully-constructed polynomials to the system, branching and exploiting symmetry.