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.

A Visual Guide to Combinatorial Search

Today, we investigate a way to visualize combinatorial search in a way that touches on most of the computational and mathematical concerns. Throughout the description, we shall refer to a common example of generating graphs using edge augmentations. Since we’ve already seen some combinatorial searches before (see Introduction to Canonical Deletion and Introduction to Orbital Branching for examples), some of this discussion will seem familiar.

Introduction to Orbital Branching

Orbital branching is an example of a method that started in combinatorial optimization but has been applied for computations in pure combinatorics. In this post, we’ll introduce this method while in the context of generating combinatorial objects. The major difference between this perspective and the original goal is that we are generating all feasible solutions (which are probably rare) while the original applications were finding optimal solutions (and feasible solutions were plentiful).

Ranking and Unranking of Combinations and Permutations

Now that we’ve discussed a nice standard example of canonical deletion, I want to get into more complicated uses. These techniques use more complicated augmentations and deletions, and hence require a little more delicate description of orbit calculations. In order to get to those, we need to be able to store and manipulate subsets of things. Another way to think of “subsets of things” is combinations, especially when we know the size of the subset.

Given a set , we will discuss the power set of all subsets of , the -subsets , the -tuples , and the -permutations . There are multiple ways to store a given subset, tuple, or permutation, but what is more important is how to store a list of information over the entire collection of these objects. My favorite method is to use a ranking function, which assigns each object an integer which I can use as an array position. Then, an unranking function will invert this process.

This area has a long history, with several different methods of ranking and unranking the objects competing for dominance in several measures of quality. My favorite measure is “readability” and/or “ease of programming” but definitely “computation speed” is important, too. However, sometimes ranking is fast and unranking is slow, sometimes the ranking and unranking is fixed to a certain order, such as lexicographic order.

Today we’ll talk about several ranking and unranking procedures, and the next post will discuss how to use these ranking/unranking functions to compute orbits of these objects for a graph with symmetry.

Introduction to Canonical Deletion

Today, I discuss McKay’s isomorph-free generation technique, commonly called canonical deletion, or canonical construction path. The technique guarantees that every unlabeled object of a desired property will be visited exactly once. The word visited means that a labeled object in the isomorphism class is generated and tested for the given property and possibly used to extend to other objects. Also, objects that do not satisfy the property are visited at most once because we may be able to use pruning to avoid generating objects that do not lead to solutions.

The canonical deletion technique is so called from its use of reversing the augmentation process in order to guarantee there is exactly one path of augmentations from a base object to every unlabeled object. Essentially, a deletion function is defined that selects a part of the combinatorial object to remove, and this function is invariant up to isomorphism. Then, when augmenting an object this augmentation is compared to the canonical deletion of the resulting object to check if this is the “correct” way to build the larger object. If not, the augmentation is rejected and the larger object is not visited. By following the canonical deletion from any unlabeled object, we can reconstruct the unique sequence of augmentations that leads from a base object to that unlabeled object. Further, this process is entirely local: it depends only on the current object and current position within the search tree. This allows the process to be effective even when parallelizing across computation nodes without needing any communication between nodes, unlike some other isomorph-free generation methods which require keeping a list of previously visited objects. Along the way, we will use a consistent example of generating a certain class of graphs to make the discussion more concrete.

An Incomplete List of Computational Techniques

Before I have a chance to populate this blog with detailed introductions to specific techniques, we should first investigate a short list of techniques that I plan to write about. Not only does this provide me with a list of posts to write, but provides you with some keywords to look up if you are in need of a computational method now. As I see it, there are four main types of techniques: Enumerative, Exhaustive, Existence, and Non-Existence.