Combinatorial Optimization Reading Group - Julián Romero

Title: Graph coloring of graphs with large girth is hard for the Nullstellensatz

Abstract:

In this talk we will discuss a method to solve combinatorial problems using hierarchies of systems of linear equations using Hilbert's Nullstellensatz. In particular, we will study the behaviour of these hierarchies for deciding the non-$k$-colorabilty of graphs. It is shown that if a graph $G$ has chromatic number $k+1$ and girth $g>>k$, then at least $g/2k$ levels of the Nullstellnesatz hierarchy are needed to detect the non-$k$-colorability of $G$.