patternMinor
Chromatic polynomial of a square
Viewed 0 times
squarechromaticpolynomial
Problem
Consider a square, ABCD. Intuitively it seemed to me that its chromatic polynomial is $\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2)$ where there are $\lambda$ colours available..
That is there are $\lambda$ ways in which a colour for A can be picked, there are $\lambda - 1$ ways for colours for B and D to be picked(B and D are adjacent to A) and $\lambda - 2$ ways for colours for C to be picked.
However using the decomposition theorem (slide 47, Example 11.33) and decomposing the square into a path of length 3 and a triangle, shows that my initial reasoning is wrong.
Could you tell me where I am going wrong with my thinking.
That is there are $\lambda$ ways in which a colour for A can be picked, there are $\lambda - 1$ ways for colours for B and D to be picked(B and D are adjacent to A) and $\lambda - 2$ ways for colours for C to be picked.
However using the decomposition theorem (slide 47, Example 11.33) and decomposing the square into a path of length 3 and a triangle, shows that my initial reasoning is wrong.
Could you tell me where I am going wrong with my thinking.
Solution
You must remember that the vertices diagonal from one another can be colored the same! Your formula does not take that into account. We can find the chromatic number of a graph via the inclusion-exclusion principle. It is a very general counting technique that allows us to count complex structures, if we can prove certain bounds on certain subsets.
The main idea is that we count all possible ways some property happens. Then we remove some "bad" items. However, we may have removed too much, and need to add back some "good" items. This goes back and forth until we've gone through all subsets.
Inclusion-exclusion principle tells us that given some ground set $|X|=n$, the number of elements of $X$ which lie in none of the subsets $A_i$ is
$$ \sum_{I \subseteq [n]} (-1)^{|I|}|A_I| \text{, where } \\ I \text{ is the set of indices in } X \text{ and } A_I = \bigcap_{i \in I} A_i$$
Let $\lambda$ be the number of colors, and let $X$ be the set of all possible colorings (i.e., $|X| = \lambda^4$), and let $$A_{e} = \{\text{coloring} : e=(i,j) \in E, \text{color}(i) = \text{color}(j) \}$$
Before we get our final polynomial, we need to count the size of our sets $A_{e}$, and the size of all intersecting subsets.
Observe that $|A_{12}| = |A_{23}| = |A_{34}| = |A_{41}| = \lambda^3$. This is due to the fact that we are just coloring $G$ but always picking the same colors for neighboring vertices. Going forward we have,
$|A_{12} \cap A_{23} | = |A_{23} \cap A_{34} | = |A_{34} \cap A_{41}| = |A_{41} \cap A_{12}| = |A_{12} \cap A_{34}| = |A_{41} \cap A_{23}| = \lambda^2$
I'm not going to list each 3-set, but they all have the same count. $|A_e \cap A_{e'} \cap A_{e''}| = \lambda$. And Finally, $|A_{12} \cap A_{23} \cap A_{34} \cap A_{41}| = \lambda$. Now lets collect our terms and add up.
$$\lambda^4 - 4\lambda^3 + 6\lambda^2 - 4\lambda + \lambda = \lambda^4 - 4\lambda^3 + 6\lambda^2 - 3\lambda$$
Now counting with inclusion-exclusion for this problem wasn't so bad because we had a simple 4-cycle. If the graph had more structure it would quickly get annoying to figure out each intersection size for all possible intersections.
The main idea is that we count all possible ways some property happens. Then we remove some "bad" items. However, we may have removed too much, and need to add back some "good" items. This goes back and forth until we've gone through all subsets.
Inclusion-exclusion principle tells us that given some ground set $|X|=n$, the number of elements of $X$ which lie in none of the subsets $A_i$ is
$$ \sum_{I \subseteq [n]} (-1)^{|I|}|A_I| \text{, where } \\ I \text{ is the set of indices in } X \text{ and } A_I = \bigcap_{i \in I} A_i$$
Let $\lambda$ be the number of colors, and let $X$ be the set of all possible colorings (i.e., $|X| = \lambda^4$), and let $$A_{e} = \{\text{coloring} : e=(i,j) \in E, \text{color}(i) = \text{color}(j) \}$$
Before we get our final polynomial, we need to count the size of our sets $A_{e}$, and the size of all intersecting subsets.
Observe that $|A_{12}| = |A_{23}| = |A_{34}| = |A_{41}| = \lambda^3$. This is due to the fact that we are just coloring $G$ but always picking the same colors for neighboring vertices. Going forward we have,
$|A_{12} \cap A_{23} | = |A_{23} \cap A_{34} | = |A_{34} \cap A_{41}| = |A_{41} \cap A_{12}| = |A_{12} \cap A_{34}| = |A_{41} \cap A_{23}| = \lambda^2$
I'm not going to list each 3-set, but they all have the same count. $|A_e \cap A_{e'} \cap A_{e''}| = \lambda$. And Finally, $|A_{12} \cap A_{23} \cap A_{34} \cap A_{41}| = \lambda$. Now lets collect our terms and add up.
$$\lambda^4 - 4\lambda^3 + 6\lambda^2 - 4\lambda + \lambda = \lambda^4 - 4\lambda^3 + 6\lambda^2 - 3\lambda$$
Now counting with inclusion-exclusion for this problem wasn't so bad because we had a simple 4-cycle. If the graph had more structure it would quickly get annoying to figure out each intersection size for all possible intersections.
Context
StackExchange Computer Science Q#4758, answer score: 8
Revisions (0)
No revisions yet.