Chromatic Polynomials 02 - Almost a Language of Logic

In the previous article, we saw that each edge in a graph represents a condition. That condition is transcribed into a term to be multiplied with other terms. The result of the summation is the number of ways that all the specified conditions can be met.

Logical NOT

In an unsummed CP, a 1 represents all the unconstrained possibilities. As shown in exercise 1a, from the previous article:

The term (1 - δ_σ1σ2) represents “All the unconstrained ways, minus the ways that σ₁ is equal to σ₂”. This shows us that in CPs, (1 - X) is the logical equivalent of NOT X.

This also means that we could take the formula from graph 1, (1 - δ_σ1σ2) (1 - δ_σ1σ3), and instead of requiring that σ₁ and σ₂ be different, we can require that they are the same by removing the NOT operation: δ_σ1σ2(1 - δ_σ1σ3).

This is also logically consistent in that NOT NOT δ_σ1σ2 = δ_σ1σ2:

Logical AND

The expression:

Could be expressed as:

All the ways that (σ₁ is not equal to σ₂) AND (σ₁ is not equal to σ₃)

In CPs, multiplying two conditions together amounts to a logical AND. To reinforce this, consider that if one of the terms is zero after all summations, then the entire solution will be zero, as a result of multiplication by zero. This is analogous to saying that if there is no way to meet one of the conditions, then the overall formula will sum to 0.

Logical OR

If two conditions, A and B, are mutually exclusive, then the ways to meet A or B is the sum of the ways:

Of course, we must carefully observe the caveat that A and B must be mutually exclusive. The generalized formula is:

If A and B are mutually exclusive, then the term AB (meaning “A AND B”) will sum to 0 and can be dropped.

De Morgan’s Laws

With more complex CPs, it can be hard to know if two conditions being OR’ed together are mutually exclusive. To ensure that the CP is well-formed, we can use De Morgan’s Laws:

A OR B = NOT ((NOT A) AND (NOT B)) = 1 - (1 - A)(1 - B)

Note that this expands to the same form shown above:

1 - (1 - A)(1 - B) = 1 - (1 - A - B + AB) = A + B - AB

And

                                    NOT (A OR B) = (NOT A) AND (NOT B) = (1 – A)(1 – B)

A few more effects

Because multiplication represents a logical AND, we should be able to see that multiplying a logical term, A, by itself will just yield A. In other words, A * A = A.

This is clear in the simplest case δ_ij² = δ_ij:

If δ_ij =1, then δ_ij² becomes 1² = 1 and δ_ij² = δ_ij.

If δ_ij = 0, then δ_ij² becomes 0² = 0 and δ_ij² = δ_ij.

With that, we can extend it to (1 – δ_ij)² = (1 – δ_ij):

(1 – δ_ij)² = (1 - 2 δ_ij + δ_ijδ_ij)

(1 – δ_ij)² = (1 - 2 δ_ij + δ_ij²)

(1 – δ_ij)² = (1 - 2δ_ij + δ_ij), since δ_ijδ_ij = δ_ij

(1 – δ_ij)² = (1 - δ_ij)

Next, with A and B representing logical terms: (A + B - AB)² = (A + B - AB):

            (A + B - AB)² = (A² + B² + A²B² + 2AB - 2A²B - 2AB²)

            (A + B - AB)² = (A + B + AB + 2AB - 2AB - 2AB)

(A + B - AB)² = (A + B - AB)

If it’s known that A and B are mutually exclusive, then we can also show that (A + B) (A + B) = (A + B):

            (A + B)² = (A² + B² + 2AB)

            (A + B)² = (A + B + 2AB)

                        Since A and B are mutually exclusive, AB = 0

            (A + B)² = (A + B +2 * 0)

            (A + B)² = (A + B)

We can also see that if (1 - A) means NOT A and multiplication means AND, then A * (1-A) means “A and NOT A” and should evaluate to 0:

            A(1-A)

            = A-A²

            = A - A

            = 0

This gives us an almost complete language of logic. It allows us to pick any two vertices in a graph and require that they be equal or unequal, then combine that term with any other requirements we want.

It is “almost complete” because there are still some gaps in the capabilities of chromatic polynomials. The exercises from the previous article, 1a - 1i, show every unique CP that can be created from a graph with four vertices. Eight of those CPs are of the form Qᵃ(Q-1)ᵇ(Q-2)ᶜ(Q-3)ᵈ, where a, b, c, and d are non-negative integers in the range 0 - 4 and

a+b+c+d=4. Exercise 1f breaks this pattern, as it is the sum of two such expressions, Q(Q-1)²+ Q(Q-1)(Q-2)² (and it’s the only case that I consider “interesting”). The largest CP, from exercise 1a, is the exponential Q⁴. The smallest CP, from exercise 1i, is the permutation, Q(Q-1)(Q-2)(Q-3) = Q Permute 4. Without expanding the language, all CPs fall somewhere between an exponential and a permutation.

Next, I will introduce enhancements to the syntax of chromatic polynomials which expand it into a fully-featured language of logic.

Previous Post:

www.solutionslookingforproblems.com

Chromatic Polynomials 01 - Introduction

Through this article and the next several articles, I’m going to share with you something called Chromatic Polynomials. It’s a form of math that is quite powerful in its most basic form, but I’ll show you how to make it even more so. I’ll show you how to apply chromatic polynomials to sudoku, logic puzzles, video poker, slot games, B-Sat problems, and more.I first learned about chromatic polynomials from the paper “Counting complex disordered states by efficient pattern matching: chromatic polyn

Next Post:

www.solutionslookingforproblems.com

Chromatic Polynomials 03 – Expanding the Capabilities

This article outlines modifications that I came up with to expand Chromatic Polynomials into a fully-capable language of logic.Constants instead of variablesThe traditional Kronecker Delta compares two variables, e.g. δij compares i and j. We could just as easily replace one of those variables with a constant value:This changes the rules for summation a little bit:That is, of all the values that i can take, only one will be 3. This allows us to specify that a vertex must match a specific value,