Title: Graph coloring of graphs with large girth is hard for the Nullstellensatz
|Affiliation:||University of Waterloo|
|Zoom:||Contact Sharat Ibrahimpur|
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$.