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.

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.

Computational Combinatorics Roundup: March 2013

I was thinking that this month was lacking any new computational combinatorics papers, but then three papers arrived in my feed within a couple days of each other, followed by several others to finish out the month. Read on to learn about them, and as always send me an email whenever you see a relevant research article or news story.

3-Uniform Friendship Hypergraphs

A very brief welcome to EXCILL2 participants. Thanks for visiting!

Today we discuss On a question of Sós about 3-uniform friendship hypergraphs by Hartke and Vandenbussche. These authors presented several new examples of friendship hypergraphs exhibiting a property that was not known to be possible. Their method applies careful use of integer programming as a black box. First, a careful construction of an integer linear program discovered some examples (and non-existence of examples) for small orders. Then, by making some symmetry assumptions, they constructed some larger integer programs that found larger examples, hinting towards an infinite family. The existence of larger examples remains open, although Lia, van Reesa, Seoa, and Singhi recently proved some structure theorems that apply to the examples found by Hartke and Vandenbussche.

A Branch-and-Cut Strategy for the Manickam-Miklós-Singhi Conjecture

Stephen Hartke and I recently uploaded our paper, A Branch-and-Cut Strategy for the Manickam-Miklós-Singhi Conjecture to the arXiv. We build a computational method to verify a conjecture involving the number of nonnegative -sums in a nonnegative sum of real numbers. With this method, we proved a stronger statement than the conjecture for all and formed a stronger conjecture.

The method makes use of linear programming techniques and software, so begins our discussion of linear and integer programming methods. Read on to discover the method and also to figure out what is going on with the picture below.

Computational Combinatorics Roundup: February 2013

In this month’s roundup, we have an article about computation in mathematics, and four research papers on wildly different problems.

New Page: Syllabus

I’ve added a new page to the top bar of the blog: a syllabus! Part of the goal of this blog is to develop a set of lecture materials for a future topics course in Computational Combinatorics. Since we are a few topics in, I thought it would be good to organize them by topic in a somewhat reasonable order (and the order I would present them in a course). As part of that effort, I have also placed a few topics on the list for future posts. Take a look!

Generating Fullerenes

Today, we discuss “Generation of Fullerenes” by Brinkmann, Goedgebuer, and McKay, recently published in the Journal of Chemical Information and Modeling. A fullerene for our purposes is a cubic planar graph where every face has length 5 or 6. However, the definition of fullerene as a molecule is valuable as well (and why this paper was published in a chemistry journal). Since we previously discussed generating cubic graphs, we could use that algorithm and restrict our output to graphs that satisfy our requirements, but this method is wasteful as there are many more cubic graphs of order than fullerenes of order . Since their method uses canonical deletion, we only need to describe our base objects and our augmentation step.

Computational Combinatorics Roundup: December-January

I’m a little late in compiling the late December to January roundup, but here we go. As always, send me an email if you have a blog post, paper, or other resource that I can put in the next roundup.

Generating Cubic Graphs

Today, we return to the canonical deletion method to generate cubic graphs. Cubic graphs are 3-regular graphs, and since the degree is constant, there are many fewer cubic graphs of order than general graphs of order . Also, since the structure of cubic graphs is very restricted, we can use custom augmentations to generate them more quickly than using an augmentation that works for general graphs.

This implementation of the method comes from Brinkmann, Goedgebeur, and McKay in their paper Generation of Cubic graphs from Discrete Mathematics and Theoretical Computer Science. By desigining custom augmentations, they are able to restrict their generation algorithm to create only connected cubic graphs. This augmenation is paired with a canonical deletion step which removes all isomorphic duplicates. Their implementation is given in the snarkhunter software, which is the current-fastest implementation to generate cubic graphs (and snarks; the generation snarks is investigated in a different paper).