Chromatic Polynomials 08 – Counting, Completing, Checking, Solving, and Iterating

20 hours ago
4 min read

Up to this point we have primary talked about defining a CP and then performing a summation over the vertices to produce a polynomial that tells us the number of solutions the CP has. We can use that single feature to perform a variety of functions - Counting, Completing, Checking, Solving, and Iterating.

Counting

The basic function of a CP is to count the number of ways that logical conditions can be met. Let’s look at this simple CP:

The logical conditions translate to:

σ₂ must be equal to 1 or 2.

σ₁, σ₂, and σ₃ must all have unique values

Performing the summations on this gives us this solution:

This tells is that there are four ways to assign the values 1-3 to the three vertices, σ₁ – σ₃, such that the logical conditions of the CP are met. This is the counting function of CPs.

Completing

We can also take the same CP and assign a value to one or more of the vertices. Now, summing the CP tells us how many ways there are to complete the assignments of the remaining vertices.

For example, we can assign σ₁ = 1. There are two ways to make this assignment. One way is to multiply the entire CP by a condition that requires that σ₁ = 1, δσ₁{1}:

Performing the summations on this CP tells us that there is only one way to assign the values:

Trying the other values, σ₁ = 2 and σ₁ = 3, gives us:

Of course, when we add these up, we get 4, the total number of solutions to the original CP.

The other way to assign a value to a vertex is to replace that vertex with the constant value. Below, we see the original CP, with σ₁ replaced with the constant 1. Note that we do not need to sum over σ₁:

There are other implications to replacing vertices with constants, which I will discuss in depth in another article.

This shows us that we can create a partial solution by assigning constant values to some of the vertices in a CP. The summations tell us how many ways there are to complete the assignments.

And remember this rule from article 3: Never use constants larger than the range being summed over.

Checking

A very interesting thing happens when we assign a value to every vertex – summing the CP will yield either 0 or 1. If the CP evaluates to 1, it means the assignments made satisfy the logical conditions represented by the CP. If the CP evaluates to 0, they do not. Given a full set of assignments, the CP becomes a checking function.

This CP assigns the values σ₁ = 1, σ₂ = 2, and σ₃ = 3 to our example CP:

Because this sums to 1, we know that σ₁ = 1, σ₂ = 2, and σ₃ = 3 is a solution.

This CP assigns the values σ₁ = 2, σ₂ = 3, and σ₃ = 1 to our example CP:

Because this sums to 0, we know that σ₁ = 2, σ₂ = 3, and σ₃ = 1 is not a solution.

Solving

To solve a CP we must find a value for each vertex that meets the requirements. This is a simple matter of repeatedly using the completion function. We start by finding a value for σ₁:

Use the completion function to see if σ₁ = 1 is part of a solution:

Since this has a positive solution, we know that σ₁ = 1 is part of a solution. We will leave that in and test values for σ₂.

Test to see if σ₁ = 1, σ₂ = 1 is part of a solution:

Since this summation yields 0, we know that σ₁ = 1, σ₂ = 1 cannot lead to a solution. We have to try a different value for σ₂. Test to see if σ₁ = 1, σ₂ = 2 is part of a solution:

This tells us that σ₁ = 1, σ₂ = 2 is indeed part of a solution. Trying the values for σ₃ will show us that the only acceptable value, given that σ₁ = 1 and σ₂ = 2, is σ₃ = 3.

This is essentially a depth-first tree traversal. The first level contains one branch for every value of σ₁, the second level contains one branch for every value of σ₂, and so on. If a value produces a CP that sums to 0, the tree stops there. When we reach the bottom level with a sum >= 1, we have found a solution.

A comment on Hollywood

I have always hated that one scene in movies where a computer is trying to hack a system and a display shows the thousands of codes flashing by with fixed values for the digits the computer has solved.

With modern cryptography – which goes back to way before War Games - you can’t guess part of a password or code. You have to guess the entire password and then see if you are right or not.

Every time I see one of these scenes, I want to yell at the TV, “It doesn’t work like that!”

Except … that is how we solve CPs. Anything that can be encoded in a CP can be solved one variable at a time. If we encode a math formula into a CP, with each vertex representing a digit, we can literally solve it one digit at a time.

That should make Hollywood happy. Or maybe just that one guy that Hollywood fired for caring about realism.

Iterating

Iterating through all solutions is as simple as traversing the entire tree. Instead of stopping when one solution is found, we explore all possibilities. This tree shows the values that lead to the four solutions to the CP: