Computational Combinatorics

Month: May, 2013

Introduction to the Nullstellensatz/Linear Algebra Method

We have spent a lot of time discussing how to generate objects, but in order for us to generate them they must exist! This idea of showing existence versus non-existence is central to the computational complexity classes of NP and coNP: the difference is whether you use an existential quantifier or a universal quantifier. So, nonexistence problems can be phrased as “All objects do not have this property” and are not suited well to proof by certificate. We can demonstrate existence by finding and presenting the object, but nonexistence is harder to prove.

Today, we discuss Computing Infeasibility Certificates for Combinatorial Problems through Hilbert’s Nullstellensatz by Jesús A. De Loera, Jon Lee, Peter N. Malkin, and Susan Margulies, where they develop what I will call the Nullstellensatz/Linear Algebra Method, or NulLA for short. Their method starts with a set of polynomials whose common roots correspond to the goal object and they build a Nullstellensatz certificate that demonstrates that a set of polynomials have no common root. The certificate is built by solving a set of linear equations. This method is greatly improved by using symmetry to reduce the size of the linear system. The authors’ main idea is to use these certificates to prove certain graphs are not 3-colorable, but I believe this can be used to prove nonexistence of combinatorial objects.
Read the rest of this entry »

Spring Happenings

It has been a month and a half since my last post, which was not intentional. However, there are a couple pretty good reasons why.

1. The semester came to a close, and together my two classes had six exams (midterms, make-ups, and finals) in a span of three weeks.

2. My wife and I accepted tenure-track jobs at Iowa State University and have been working hard making plans for the move this summer.

Thanks for your patience and I hope to be back on topic very soon.