Chromatic Polynomials 10 – Simplifying Before Summing

4 hours ago
5 min read

There are a few ways to simplify a CP before summing it.

Replacing a Vertex with a Constant

If the entire CP is multiplied by a term that constrains a svertex to a single constant, e.g. δσ₅{2}, we can remove that term and instead replace all instances of σ₅ with the constant 2.

Examples:

δσ₅{2}(1 - δσ₄σ₅) becomes (1 - δσ₄{2})

δσ₅{2}δσ₄σ₅σ₆ becomes δσ₄σ₆{2}

δσ₅{2}δσ₄σ₅{2-5} becomes δσ₄{2}

δσ₅σ₆{2}δσ₄σ₅σ₆{2-5} becomes δσ₄{2}

δσ₅{2}δσ₅{2-5} becomes 1

δσ₅{2}δσ₅{3} becomes 0

δσ₅{2}δσ₄σ₅{3-5} becomes 0

When replacing a vertex with a constant, we no longer sum over that vertex. In this example, replacing δσ₄with 2 means we no longer sum σ₄ from 1 to 3:

Why must the constraint apply to entire CP?

If a CP contains two parts and only one part constrains a vertex to a single constant, replacing the vertex with the constant can lead to confusion and wrong results. For example, in this CP, the first half constrains δσ₄ to 2, but the second half does not:

Replacing the vertex in the first half would produce this:

Do we sum σ₄ from 1 to 3 or not? Summing σ₄ from 1 to 3 yields 126. Summing only σ₁through σ₃ from 1 to 3 yields 42. Both answers are wrong!

The answer becomes clear if we first separate the CP into two summations:

Now we can replace the vertex σ₄ with a constant 2 in the first summation and leave the second summation unchanged:

The left half sums to 24. The right half sums to 54. Those add up to 78, which matches our first answer.

Thus, it is only safe to replace a vertex with a constant if that vertex is constrained to the constant value for the entire CP.

Can a vertex be replaced with a set of constants?

This can produce inconsistent and incorrect results. Take this CP:

If we replace σ₂ with {3-5} we will get this if we include σ₂ in the summation:

And this if we exclude σ₂ from the summation:

More complicated CPs provide even more opportunities for this to go wrong.

A vertex should only be replaced with a single constant, and only when the vertex is constrained to that constant for the entire CP.

Replacing an Exclusive Term with an Inclusive Term

I call terms that contain a NOT operation exclusive terms, since they are explicitly excluding some arrangement of values. One example is (1- δσ₄{2}), which excludes all ways that σ₄ = 2.

I call terms without a NOT operation inclusive terms. The term δσ₄{2} is inclusive since all solutions must include σ₄ = 2.

We can replace an exclusive term with an inclusive term under two conditions:

1) The summation must be over a fixed range, e.g. 1 to 3. The summation cannot be from 1 to Q, or any other variable to be filled in later.

2) The EKD in the exclusive term must contain exactly one vertex.

We perform the replacement by removing the “NOT” and replacing the set of constants with its complement in the summation set.

For example, if summing from 1 to 3, the summation set is {1, 2, 3}. We convert (1- δσ₄{2}) by removing the (1 - ) and replacing {2} by its complement in {1, 2, 3}, which is {1, 3}:

(1- δσ₄{2}) becomes δσ₄{1,3}

Why must the summation be over a fixed range?

If summing (1- δσ₄{2}) from 1 to Q, we don’t know how high Q goes. If Q is 3, then the complement to {2} is {1, 3}. If Q is 4, the complement to {2} is {1, 2, 4}. We can’t replace [2} with its complement unless we know the exact range we are summing over.

Why must the EKD contain exactly one vertex?

An EKD must always contain at least one vertex. An EKD that only compares constants can be resolved immediately and replaced with 0 or 1. Let’s look at an EKD with two vertices:

δσ₁σ₂{3-5} means that σ₁= σ₂ AND that both are equal to 3, 4, or 5.

Its opposite, (1 - δσ₁σ₂{3-5}), means that either σ₁≠ σ₂ OR that they are equal to 1 or 2.

δσ₁σ₂{1-2} means that σ₁= σ₂ AND they are equal to 1 or 2.

Thus, we cannot replace (1 - δσ₁σ₂{3-5}) with δσ₁σ₂{1-2}.

As further evidence, let’s look at the sum for δσ₁σ₂{1-2}:

This is not the same as our original sum, 22.

We can only replace an exclusive term with an inclusive term if that term contains only one vertex.

Combining EKDs

As shown in Chromatic Polynomials 03 - Expanding the Capabilities (https://www.solutionslookingforproblems.com/post/chromatic-polynomials-03-expanding-the-capabilities), EKDs that are multiplied together can be combined if they share at least one vertex. The resulting EKD contains the union of the vertices and the intersection of the constants of the two original EKDs:

A Simplification Exercise

Let’s revisit the first logic puzzle from the previous article:

Fred, Harry, and Morty are all traveling on the same train. The person in seat 95C is happy to not be in third class. Harry was not happy to be in seat 74D. All seats numbered from 1 to 35 are first class. Fred's seat has a larger number.

We assign these values to the names, seats, and classes:

Names	Classes	Classes
Fred = 1 Harry = 2 Morty = 3	FirstClass = σ₁ SecondClass = σ₂ ThirdClass = σ₃	Seat34A = σ₆ Seat74D = σ₇ Seat95C = σ₈

And we created this CP to represent the logic problem:

Note that the entire CP is constrained by the term δσ₅{2}, which means that σ₅ must be equal to 2. Instead of using the term δσ₅{2}, we can replace σ₅ with 2. This gives us:

Remember that we have to remove σ₅ from the summation, saving us some work.

We can replace the exclusive (1- δσ₄{1}) with the inclusive δσ₄{2,3}, replace (1- δσ₄{2}) with δσ₄{1,3}, and replace (1- δσ₆{2}) with δσ₆{1,3}:

We can also combine δσ₁σ₄, δσ₄{1,3}, and δσ₄{2,3} into one EKD:

This shows us that σ₁ and σ₄ are both equal to 3. We can replace those vertices with the constant, 3:

This gives us three more exclusive terms that can be converted to inclusive terms:

Now we can combine the EKDs that contain σ₆:

With σ₆ constrained to 1, we can replace it with 1 and remove it from the summation:

Now we have an exclusive term to convert to an inclusive term:

Combining the EKDs with σ₃ yields:

Replacing σ₃ with 2 gives us:

Converting the last exclusive term to an inclusive term produces:

Combining the last two EKDs:

Replacing that last vertex with a constant brings us to:

1, where σ₁ = 3, σ₂ = 1, σ₃ = 2, σ₄ = 3, σ₅ = 2, σ₆ = 1

This reduces our entire logic problem expression to 1, needing no summations. It shows us that the number of solutions is 1 and that the solution is:

σ₁ = 3

σ₂ = 1

σ₃ = 2

σ₄ = 3

σ₅ = 2

σ₆ = 1

Translating those back to their meaning in original problem gives us this:

First Class = σ₁ = 3 = Morty

Second Class = σ₂ = 1 = Fred

Third Class = σ₃ = 2 = Harry

Seat 34A = σ₄ = 3 = Morty

Seat 74D = σ₅ = 2 = Harry

Seat 95C = σ₆ = 1 = Fred

This matches the solution we found previously:

Fred = Second Class = Seat 95C

Harry = Third Class = Seat 74D

Morty = First Class = Seat 34A

This example is almost too clean, but it shows us that we can simplify CPs and avoid some summations by performing these steps wherever possible:

Replacing a vertex with a constant, and removing that vertex from the summation.
Replacing exclusive terms with inclusive terms.
Combining EKDs where possible.

Previous Post: