The Chromatic Polynomial - Study Guide

THE CHROMATIC POLYNOMIAL Abstract. It is shown how to compute the Chromatic Polynomial of a simple graph utilizing bond lattices and the Möbius Inversion Theorem, which requires the establishment of a refinement ordering on the bond lattice and an exploration of the Incidence Algebra on a partially ordered set. 1. Introduction A common problem in the study of Graph Theory is coloring the vertices of a graph so that any two connected by a common edge are different colors. The vertices of the graph in Figure 1 have been colored in the desired manner. This is called a Proper Coloring of the graph. Frequently, we are concerned with determining the least number of colors with which we can achieve a proper coloring on a graph. Furthermore, we want to count the possible number of different proper colorings on a graph with a given number of colors. We can calculate each of these values by using a special function that is associated with each graph, called the Chromatic Polynomial. For simple graphs, such as the one in Figure 1, the Chromatic Polynomial can be determined by examining the structure of the graph. For other graphs, it is very difficult to compute the function in this manner. However, there is a connection between partially ordered sets and graph theory that helps to simplify the process. Utilizing subgraphs, lattices, and a special theorem called the Möbius Inversion Theorem, we determine an algorithm for calculating the Chromatic Polynomial for any graph we choose. Figure 1. A simple graph colored so that no two vertices connected by an edge are the same color. 1 2 Figure 2. N3 : A null graph on 3 vertices. Figure 3. K3 : The complete graph on 3 vertices. 2. Basics of Graph Theory 2.1. Basic Definitions. The basic definitions of Graph Theory, according to Robin J. Wilson in his book Introduction to Graph Theory, are as follows: • A graph G consists of a non-empty finite set V (G) of elements called vertices, and a finite family E(G) of unordered pairs of (not necessarily distinct) elements of V (G) called edges. • V (G) is called the vertex set and E(G) is called the edge family of G. • If an edge is the unordered pair {v, w}, the edge is said to join the vertices v and w and is labeled vw. • Two vertices v and w of a graph G are said to be adjacent if there is an edge vw joining them; the vertices v and w are also said to be incident with the edge vw. • The degree of a vertex v of a graph G is the number of edges incident with v. • A simple graph is one in which there is at most one edge joining a given pair of vertices and there are no loops, or edges joining a given vertex with itself. • A graph is connected if for each pair of vertices u, v there is a sequence of vertices v0 , v1 , v2 , . . . vn , where v0 = u and vn = v, such that vi vi+1 is an edge, where 0 ≤ i ≤ n − 1. With these definitions, we can now describe specific types of graphs. • A null graph is one in which the edge family, E(G) is empty. A null graph of n vertices is denoted by Nn . See Figure 2. • A complete graph is a simple graph in which each pair of distinct vertices are adjacent. Complete graphs on n vertices are denoted by Kn . See Figure 3. THE CHROMATIC POLYNOMIAL 3 Figure 4. C4 : A cycle graph on 4 vertices. Figure 5. P3 : A path graph on 3 vertices. • A connected graph in which the degree of each vertex is 2 is a cycle graph. A cycle graph of n vertices is denoted by Cn . See Figure 4. • A path graph on n vertices is the graph obtained when an edge is removed from the cycle graph Cn . A path graph of n vertices is denoted Pn . See Figure 5. Next, we discuss graph coloring. Particularly, we are interested in determining the number of ways we can color the vertices of a graph with a given number of colors so that no two adjacent vertices are the same color. The following definitions describe graph colorings: • A coloring of a graph G so that adjacent vertices are different colors is called a Proper Coloring of the graph. • A graph G is k-colorable if we can assign one of k colors to each vertex to achieve a proper coloring. • A graph G is k-chromatic or has chromatic number k if G is k-colorable but not (k − 1)-colorable. Symbolically, let χ be a function such that χ(G) = k, where k is the chromatic number of G. We note that if χ(G) = k, then G is n-colorable for n ≥ k. 2.2. Chromatic Polynomials. Now, we discuss the Chromatic Polynomial of a graph G. This is a special function that describes the number of ways we can achieve a proper coloring on a graph G given k colors. If G is a simple graph, we write PG (k) as the number of ways we can achieve a proper coloring on the vertices of G given k colors and PG is called the Chromatic Function of G. If k < χ(G), then PG (k) = 0. If we want to color the null graph N3 with k colors, we notice that this can be done k 3 ways because there are k color options for each vertex since no vertex is adjacent to another (See Figure 6). In general, we know that PNn (k) = k n . 4 Figure 6. Calculating the Chromatic Function of N3 . Figure 7. Calculating the Chromatic Function of P3 . Figure 8. Calculating the Chromatic Function of K3 . For the path graph P3 , we start with an end vertex and note that this vertex can be colored in k ways. As we move across the graph to the right, each successive vertex can be colored (k − 1) ways as it cannot be the same color as the vertex to its left (See Figure 7). Thus, P3 can be colored k(k − 1)2 ways with k colors. In general, PPn (k) = k(k − 1)n−1 . For the complete graph K3 , we begin by selecting a random vertex and note that it can be colored k ways. If we move from this vertex to any other, we notice that this second one can only be colored k − 1 ways as it is adjacent to the first. The third and final vertex can only be colored k − 2 ways as it is adjacent to both of the first two (See Figure 8). As a result, we find that K3 can be colored k(k − 1)(k − 2) ways with k colors. In general, PKn (k) = k(k − 1)(k − 2) · · · (k − n + 1). For many graphs, it is very difficult to determine the Chromatic Functions by analysis of the structure of the graphs, as is done above. However, the following theorem provides a method for computing these functions by deleting an edge in the graph and then contracting the vertices connected by this edge. When we contract two vertices, we identify them as a single vertex and all edges incident with either vertex become incident with both. THE CHROMATIC POLYNOMIAL 5 Figure 9. The figure described in the proof of Theorem 1. Theorem 1. Let G be a simple graph, and let G − e and G/e, respectively, be the graphs obtained from G by deleting then contracting an edge e. Then PG (k) = PG−e (k) − PG/e (k). Proof. We utilize Figure 9 as a reference. Let e = vw. The number of k-colorings of G − e in which v and w have different colors is the same with or without edge e and is thus equal to PG (k). Similarly, the number of k-colorings of G − e in which v and w are the same color does not change regardless of whether the two vertices are contracted; this number is thus equal to PG/e (k). We note that the graph G/e may not be be a simple graph, but because v and w are distinct vertices we know that the contraction will not create any loops. Also, we can ignore multiple edges between vertices as this does not affect the calculation of the Chromatic Polynomial (as two adjacent vertices remain adjacent regardless of the number of edges between them). As a result, we find that the total number of k-colorings of G−e is PG (k)+PG/e (k). Subtraction yields PG (k) = PG−e (k) − PG/e (k) as desired.  We notice that in Figure 9, G and G/e are both complete graphs. As a result, we can easily compute PG (k) and PG/e (k) based on the algorithm given above. Thus, PG (k) = k(k − 1)(k − 2)(k − 3) and PG/e (k) = k(k − 1)(k − 2). The Chromatic Polynomial for G − e is more difficult to compute, however we can use our recursion formula to find that PG−e (k) = PG (k)+PG/e (k) = k(k−1)(k−2)(k−3)+k(k−1)(k−2) = k(k−1)(k−2)2 , as expected. With Theorem 1, we can now prove that the Chromatic Function of a graph G is a polynomial. We note that all of the graphs included in the rest of this paper are simple graphs, so the following theorem relates strictly to these. Theorem 2. The Chromatic Function of a simple graph is a polynomial. Proof. We again utilize Figure 9 as a reference. As we did with G, we pick edges in G − e and G/e and delete and contract them. We then repeat the process with the four new graphs we have and so on. The process terminates when all of the remaining graphs are null graphs. Because the Chromatic Function of a null graph is a polynomial (PNn (k) = k n ), we see that the Chromatic Function of G is equal to the sum of a large number of polynomials and must itself be a polynomial. We thus refer to the Chromatic Function as the Chromatic Polynomial.  6 If we compare the chromatic polynomials of N3 , P3 , and K3 , we notice that they have some interesting properties. PN3 (k) = k 3 PP3 (k) = k(k − 1)2 = k 3 − 2k 2 + k PK3 (k) = k(k − 1)(k − 2) = k 3 − 3k 2 + 2k. In each of the polynomials above we notice that there is no constant term. Thus, if k = 0, P (k) = 0, as we would expect. Also, except in the case of the null graph, we notice that the sum of the coefficients of each polynomial is 0, which tells us that P (1) = 0. This, again, is as expected because any graph with more than 1 vertex and at least one edge cannot be properly colored with only 1 color. Our final two observations are that the coefficients of these polynomials have alternating signs and that the absolute value of the coefficient on the term k n−1 is the number of edges of the graph. We prove that these characteristics are common to the Chromatic Polynomials of all graphs in Section 8. 3. Partially Ordered Sets 3.1. Basic Definitions and Properties. For some graphs, the method in Theorem 1 is either inefficient or too tedious to use for computing the Chromatic Polynomial. However, we can use partition lattices and a special function called the Möbius Function to find these polynomials. First, we consider partially ordered sets. According to E.A. Bender and J.R. Goldman, a partially ordered set Q = (S, ≤) is a pair consisting of a set S and a binary relation ≤ on S that satisfies the following properties: (1) Reflexivity: For all x ∈ S, x ≤ x. (2) Antisymmetry: Given any x, y ∈ S, if x ≤ y and y ≤ x, then x = y. (3) Transitivity: For all x, y, z ∈ S, if x ≤ y and y ≤ z, then x ≤ z. If the binary relation on the set S is irreflexive, that is for all x ∈ S, x 6≤ x, as well as antisymmetric and transitive, Q is called a strict partial ordering. We also note that in a partially ordered set, two elements x and y may be incomparable if x ≤ y is false and y ≤ x is also false. If for every two elements w and z in a partially ordered set either w ≤ z is true or z ≤ w is true, then the partially ordered set is called a linearly ordered set or a chain. An interval [u, v] is the set of all elements between u and v. Thus, [u, v] = {t ∈ S|u ≤ t ≤ v}. A partially ordered set is locally finite if every interval contains a finite number of elements. Two partially ordered sets, (S, ≤) and (S 0 , ≤0 ), are isomorphic if they differ only by a labeling of their elements and ordering relation; this relationship is written (S, ≤) ∼ = (S 0 , ≤0 ). More specifically, we say that (S, ≤) ∼ = (S 0 , ≤0 ) if and only if there 0 is a one-to-one onto map φ : S → S such that x ≤ y if and only if φ(x) ≤0 φ(y). Now, suppose Q is a partially ordered set and let q and r be elements of Q. If x is another element of Q such that x ≤ q and x ≤ r, then x is called a lower bound of q and r. If v is a lower bound of q and r such that x ≤ v for all other lower bounds x, then v is the greatest lower bound or meet of q and r. Similarly, an element y such that q ≤ y and r ≤ y is called an upper bound of q and r. If u is an element such that u ≤ y for all other upper bounds y, then u is the least upper bound or join of q and r. A partially ordered set with the property that every pair of elements has a meet and a join is called a lattice. The ordering on a THE CHROMATIC POLYNOMIAL 7 Figure 10. The physical representation of the divides lattice on the set {1, 2, 3, 4, 6, 12}. lattice can be represented physically, as is the case with the “divides” relation on the set {1, 2, 3, 4, 6, 12} in Figure 10. 3.2. Partitions. A partition of a set R is defined to be a set of subsets of R which are disjoint and whose union is R. Each element of a partition is known as a part. As an example, let R = {1, 2, 3, 4}. Two different partitions of R, which we label P and Q, are P = {{1, 2}, {3}, {4}} and Q = {{1, 2, 3}, {4}}. Two different parts in P are {1, 2} and {3}. Given partitions P and Q of a set R, we can define a relationship between them in which we say that P is finer than Q if every subset, or part, in P is a subset of a subset (part) in Q, where P 6= Q. We denote this relationship by P ≺ Q. Also, within this relationship we say that Q is coarser than P . In our example, we see that P ≺ Q because {1, 2} ⊆ {1, 2, 3}, {3} ⊆ {1, 2, 3}, and {4} ⊆ {4}. This relationship is known as the Refinement ordering on the partitions of a set. In the following theorem, we show that the ordering is actually a strict partial ordering. Theorem 3. The Refinement ordering on the partitions of a set R is a strict partial ordering, that is the following three properties hold: Irreflexivity, for all partitions P , P 6≺ P ; Antisymmetry, for all partitions P and Q, if P ≺ Q, then Q 6≺ P ; and Transitivity, for all partitions P , Q, and S, if P ≺ Q and Q ≺ S, then P ≺ S. Proof. We first prove irreflexivity. This property is given in the definition of the relationship. If P ≺ Q is true, then P 6= Q; thus, P 6≺ P . To prove antisymmetry, let P and Q be partitions of a set R such that P ≺ Q. Now, suppose that Q ≺ P . Let q1 be an arbitrary part of Q. Because Q ≺ P , we know that there exists some p ∈ P such that q1 ⊆ p. Also, because P ≺ Q, we know that there exists some q2 ∈ Q such that p ⊆ q2 . By transitivity of ⊆, this means that q1 ⊆ q2 . However, because Q is a partition, all of its parts are disjoint. Thus, q1 ⊆ q2 means that q1 = q2 . Now, we have q1 ⊆ p and p ⊆ q1 , which means that q1 = p. It we choose an arbitrary part p1 in P , we can use a similar argument to show that p1 = q, where q ∈ Q. We conclude that P = Q. However, this is a contradiction by irreflexivity. Thus, Q 6≺ P . 8 Figure 11. The partition lattice for the set R. Now, let P , Q, and S be partitions of a set R such that P ≺ Q and Q ≺ S. We will prove transitivity by showing that P ≺ S. Let p ∈ P . Then, there exists some q ∈ Q such that p ⊆ q. Also, because Q ≺ S, there exists some s ∈ S such that q ⊆ s. By transitivity of ⊆, we have p ⊆ s. We also note that P 6= S because then we would have P ≺ Q and Q ≺ P , a violation of the property of antisymmetry. Thus, we conclude P ≺ S.  For the purposes of the partially ordered sets we will use to compute the Chromatic Polynomial, we allow the Refinement Ordering to be reflexive. In this case, the ordering is denoted  and we can have P  P . Given all possible partitions of a set R, we can create a partition lattice which organizes the partitions based on the relationship ≺, with the “finest” partitions at the bottom of the lattice and the “coarsest” at the top. In the partition, a line is drawn from the partition P to the partition Q given that P ≺ Q and there does not exist R such that P ≺ R ≺ Q. We show that this arrangement of the partitions actually forms a lattice by demonstrating that for any two partitions P and Q, there exists a meet V and a join U of the two partitions, where U and V are also partitions of the set R. The meet V will be a partition of the elements of R such that the element x ∈ R appears in the part of V that is the intersection of the parts of P and Q in which x appears. We know such a partition will exist as the partition of R in which every element is in a separate part is finer than all other partitions. The join U of P and Q will be the finest partition of R such that such that for all parts pi of P there exists part ui of U such that pi ⊆ ui and the same is true for all parts qi of Q. We know that such a partition U must exist as the whole set R is the coarsest partition of the set and thus coaser than all other partitions. An example of a partition lattice of the set R = {1, 2, 3} is given in Figure 11. We now extend the idea of partitions and partition lattices to Graph Theory. A bond of a graph G is a partition of its vertices such that all vertices in the same part are connected within the graph (meaning that they are adjacent or there exists a path between them in the graph that includes only other vertices in the same part). The set of bonds of a graph form the bond lattice. An example of a graph and its bond lattice is given in Figure 12. THE CHROMATIC POLYNOMIAL 9 Figure 12. A graph and its bond lattice. The bond of a coloring of a graph is a partition of the vertices such that vertices in the same part are connected through a monochromatic walk, meaning that vertices in the same part are colored the same color. 4. Incidence Algebra 4.1. The Zeta and Möbius Functions. Considering a partially ordered set P , we now look at functions we can define on this set. A function f on P maps P × P , the direct product of the elements of P , to R, the set of real numbers. We can add and multiply these functions, thus forming an algebra which we refer to as the Incidence Algebra. For most functions in this Incidence Algebra, f (x, y) = 0 if x 6≤ y in P . The most basic of these functions is the Zeta Function. Sometimes referred to as the Indicator Function, it “indicates” whether or not a ≤ b in the set P . The function ζ(a, b) is defined as follows:  0 if a 6≤ b ζ(a, b) = 1 if a ≤ b. Given the partially ordered set P of n elements and a lattice that displays the ordering of the set, we use the Zeta function to create an n × n matrix that contains the values of ζ(a, b) for all a, b in the set P . In this Zeta Matrix, each column and each row is labeled with the name of an element in P . A particular entry in the matrix will be ζ(a, b), where a is the element corresponding to the row of the entry and b is the element corresponding to the column. The Zeta matrix is constructed so that the elements that appear lower in the lattice correspond to the rows closest to the top of the matrix and the columns farthest to the left. To demonstrate this idea, we look at the set P = {a, b, c, d}, with the lattice given in Figure 13. Using the Zeta Function and this lattice, we construct the Zeta Matrix in Figure 14. Another function that we can define on a partially ordered set P is called the Möbius Function. If a and b are elements of the set P , the Möbius Function µ(a, b) is defined as follows:  if a = b  1 0 P if a 6≤ b µ(a, b) =  − c:a≤c m. We also see that this sum is finite because our partially ordered set is locally finite. Next, we substitute this into the right side of the equation for Ne (x). X X X Na (y)µ(x, y) = Ne (z)µ(x, y). y:y≥x x≤y y≤z≤m The next step is to notice X X XX Ne (z)µ(x, y) = Ne (z)ζ(y, z)µ(x, y) x≤y y≤z≤m x≤y z because ζ(y, z) = 0 if y 6≤ z and Ne (z) = 0 if z 6≤ m. Rearranging the summands, we find XX X X Ne (z)ζ(y, z)µ(x, y) = Ne (z) µ(x, y)ζ(y, z). x≤y z z x≤y P However, we know x≤y µ(x, y)ζ(y, z) = δ(x, z). Thus, X X X Ne (z) µ(x, y)ζ(y, z) = Ne (z)δ(x, z). z x≤y z Because δ(x, z) = 1 when z = x and 0 otherwise, we see that X Ne (z)δ(x, z) = Ne (x). z THE CHROMATIC POLYNOMIAL 13  The Möbius Inversion Theorem II is nearly identical to the Möbius Inversion Theorem I, except that it refers to NA (read “N sub at most”) rather than Na . Theorem 5. Let Ne (x) be a real-valued function defined for all x in a locally finite partially ordered set (S, ≤) and assume there is an element l ∈ S such that Ne (x) = 0 when x 6≥ l. Define NA (x) by X Ne (y). NA (x) = y:y≤x Then Ne (x) = X µ(y, x)NA (y). y:y≤x Proof. The proof of this theorem is analogous to the proof of the Möbius Inversion Theorem I.  6. Examples of Möbius Inversion In order to better understand Möbius Inversion, we make a slight diversion to consider three examples that utilize the Möbius Inversion Theorem. We need the following definitions to proceed. If, in a locally finite partially ordered set P , x ≤ y ≤ z ≤ w, then µ(y, z) in P equals µ(y, z) in [x, w]. Now, let P = (S1 , ≤1 ) and Q = (S2 , ≤2 ) be partially ordered sets. The direct product Σ = P × Q of P and Q is the partially ordered set (S, ≤), where (1) S = S1 × S2 = {(a, b)|a ∈ S1 , b ∈ S2 }, (2) a ≤ b in Σ if and only if a1 ≤1 b1 and a2 ≤2 b2 , where a = (a1 , a2 ) and b = (b1 , b2 ). From the definition of the direct product, we can understand the Product Theorem. Product Theorem: If P has Möbius Function µ1 and Q has Möbius Function µ2 , then the Möbius Function µ of P × Q is given by µ((x1 , x2 ), (y1 , y2 )) = µ1 (x1 , y1 )µ2 (x2 , y2 ). 6.1. Connected Graphs. A connected graph is defined as a graph in which, for any two vertices, there is a walk between them. Using Möbius Inversion, we wish to count the number of possible connected graphs on a given set of vertices. We begin by noting that each graph is a union of its connected components. Also, connected components of a graph G are disjoint and therefore form a partition of the vertex set of G. This is referred to as the connected component partition of the graph G. Let V be a vertex set. Next, for each partition P of V , let N (P) be the number of graphs whose connected component partition is P. In terms of the Möbius Inversion Theorem, we think of N (P) as Ne (P). To determine the number of possible connected graphs on the vertex set, we need to calculate Ne ({V }). We find the following formula: 14 v Ne (P) = 2(2) . X P:P is a partition of V The right hand of this formula represents the total number of graphs that we can construct on the vertex set V of v elements. This is equal to the left side, which sums the number of graphs having a certain connected component partition over all possible connected component partitions. Now, if we consider a specific partition of V , say Q, if we add up Ne (P) for all partitions P finer than or equal to Q, we should get the total number of graphs whose connected componenet partitions are contained in Q. This sum is the number of graphs all of whose edges connect two vertices in one of the parts Ci of Q. By the product principle, this is the number of graphs all of whose edges are in C1 multiplied by the number of graphs all of whose edges are in C2 multiplied by...etc. If each Ci has size ci , then X Ne (P) = k Y ci 2( 2 ) . i=1 P:PQ Using Möbius Inversion, we find Ne (Q) = X µ(P, Q) j Y bi 2( 2 ) i=1 P:PQ where bi is the size of the each class Bi for each P. We want N ({V }), so we find X N ({V }) = µ(P, {V }) P:P{V } j Y bi 2( 2 ) . i=1 Because all partitions of V are finer than {V }, we can use the partition lattice to compute all the values of the Möbius Function in this formula. As an example, we consider the vertex set V = {1, 2, 3}. The partition lattice for this set is the same as the bond lattice for the complete graph on 3 vertices. This lattice is in Figure 17 with µ(x, {V }) calculated for each partition x in the lattice. Now, we can use the formula for N ({V }) to find the total possible number of connected graphs on this vertex set. N ({V }) = X P:P{V } µ(P, {V }) j Y bi 1 1 1 2 1 3 2( 2 ) = 2(2(2) ·2(2) ·2(2) )−3(2(2) ·2(2) )+1(2(2) ) = i=1 3 2(1) − 3(2) + 2(2) = −4 + 23 = 4. Thus, there are 4 possible connected graphs on the vertex set V = {1, 2, 3}. 6.2. Classical Möbius Inversion. Using the Möbius Inversion Theorem, we wish to solve the following problem: Let f (n) be a function defined on the positive integers and define X h(n) = f (k). k|n We wish to invert the sum to solve for f (n) in terms of h. THE CHROMATIC POLYNOMIAL 15 Figure 17. The partition lattice for the vertex set V = {1, 2, 3} with the Möbius Function values included. To continue, we must first consider the set S, the set of integers with the usual ordering, and the Möbius function defined over S in the following manner:  when n = k  1 −1 when n + 1 = k µ(n, k) =  0 otherwise. Now, let n be an integer and define D(n) as a the set of divisors of n. By the αs 1 Unique Factorization Theorem, D(n) ∼ = D(pα 1 ) × ... × D(ps ), where each pi is α1 αs a prime and n = p1 · · · ps . Hence, in the Möbius Function, we can calculate µ on D(pα ). However, D(pα ) is the chain 1|p|p2 · · · |pα , which is isomophic to the integers in the set S as we can map each pi to i and order the pi with regards to i. Thus,  when i = j  1 −1 when i + 1 = j µ(pi , pj ) = µ(i, j) =  0 otherwise. Now, let Qsa and b be integers. Qs We know we can factor a and b into primes so that a = i=1 pai i and b = i=1 pbi i , where each pj is a prime. By the Product Theorem, Y  s s Y µ(a, b) = µ pai i , pbi i  i=1 i=1 P (bi −ai ) (−1) if bi − ai = 0 or 1 for all i 0 bi − ai > 1 for some i.   b From this, we can deduce that µ(a, b) = µ 1, a . To understand this result, suppose = µ(pa1 1 , pb11 ) · · · µ(pas s , pbss ) = px = a and py = b, then py−x = ab . Now, µ(a, b) = µ(px , py ). By the result above this is nonzero only if x = y or x + 1 = y. However, if x = y, then py−x = p0 ; if x + 1 = y, then py−x = p. Because 1 = p0 , we see that µ(1, ab ) = µ(p0 ,px−y ), which is nonzero only if px−y = p0 or px−y = p. Thus, µ(a, b) = µ 1, ab . For 16 convenience, we simply denote µ(1, ab ) as simply µ( ab ). Now for any n, we define µ(n) as follows:  if n = 1  1 (−1)k if n is a product of k distinct primes µ(n) =  0 if a square divides n. Now, using the Möbius Inversion Theorem, we find X X n f (n) = µ(k, n)h(k) = µ h(k). k k|n k|n 6.3. The Euler Phi-Function. The Euler phi-function, φ(n), for some positive integer n, is the number of positive integers x less than or equal to n which are relatively prime to n (in other words, the number of integers x less than or equal to n such that gcd(n, x) = 1). We will use Möbius Inversion to determine an eloquent formula for computing φ(n). In terms of the Möbius Inversion Theorem, let Ne (n) = φ(n). To find NA (n), we divide the set [n] = {1, 2, ..., n} according to the gcd with n. Thus, let Sd = {i ∈ [n]|gcd(i, n) = d}. The sets P Sd are mutually disjoint and their union will be [n]. As a result, we find that n = d|n |Sd |. However, we note i ∈ Sd if and only if i = kd, where k ≤ i and gcd(k, nd ) = 1. This guarantees that each Sd is mutually disjoint and also provides a method for computing the elements of Sd . For each d we compute nd and then determine all k such that gcd(k, nd ) = 1.PFor each k, the element kd is in Sd . Thus, we note that |Sd | = φ( nd ) and n = d|n φ( nd ) = P 0 d0 |n φ(d ) = NA (n). Using the Möbius Inversion Formula, we find Ne (n) = φ(n) = X n X n n n n µ NA (d) = µ d=n− − − ··· + + ··· , d d p1 p2 p1 p2 d|n where µ( nd ) is non-zero only n d = p1 ···p . Thus, we find i d|n if n d is a product of distinct primes. If this is true, then φ(n) = n Y p|n 1− 1 . p 7. Möbius Inversion and the Chromatic Polynomial 7.1. Example 1. We now apply the Möbius Inversion Theorem to the problem of determining the Chromatic Polynomial of a graph. Let G be the graph given in Figure 18. Based on our figure, we see that the Chromatic Polynomial of G is PG (k) = k(k − 1)(k − 2)2 = k 4 − 5k 3 + 8k 2 − 4k. This should be the same result yielded by the Möbius Inversion Theorem. In order to proceed, we need the bond lattice of the graph G, so that we have an ordering on the bonds of the vertices of G. The bond lattice is given in Figure 19. Also, we need to define the functions Ne and Na for any bond b. The function Ne (b) represents the number of colorings on the vertices of G that have exactly b as their bond representation. The function Na (b) represents the number of colorings on the vertices of G that have at least b as their bond; that is, all colorings whose exact bond representation is the same or coarser than b. For any bond b and any THE CHROMATIC POLYNOMIAL 17 Figure 18. The graph G and a demonstration of the computation of its Chromatic Polynomial. Figure 19. The bond lattice of the graph G. number of colors k, Na (b) = k i , where i is the number of parts of the bond b. This is because our only restriction on the coloring is that bonds in the same part must be the same color; we are not concerned with adjacent vertices or vertices in different parts colored different colors. As a result, there are are k ways to color each part of the bond, yielding k i ways to color a bond with i parts. To calculate the Chromatic Polynomial of G, we need to calculate Ne ({{1}, {2}, {3}, {4}}) as the bond {{1}, {2}, {3}, {4}} represents all colorings in which no two adjacent vertices are the same color. Let P this bond be denoted by P , then by the Möbius Inversion Theorem, Ne (P ) = Q:P Q µ(P, Q)Na (Q). As a result, for each bond Q in the lattice, we evaluate µ(P, Q). In our lattice, we assign each bond its respected value. See Figure 20. 18 Figure 20. The bond lattice of the graph G, with the Möbius Function values included. We notice that all bonds on the same level of the lattice have the same number of parts. Thus, for all bonds Q on the same level, Na (Q) = k i , where i is the common number of parts. We can then sum up the Möbius Function values for all the bonds on a particular of k i in our sum. P level and use this value as4the coefficient 3 2 We find that Ne (P ) = Q:P Q µ(P, Q)Na (Q) = k − 5k + 8k − 4k, which is, in fact, PG (k). 7.2. Example 2. As a further application of the Möbius Inversion Theorem to Chromatic Polynomials, we compute the Chromatic Polynomial of the cycle graph given in Figure 21. In order to accomplish this task, we first set up the bond lattice of this graph as shown in Figure 22. As in our previous example, we need to compute Ne ({{1}, {2}, {3}, {4}, {5}} in order to find the Chromatic Polynomial of the graph. Let the bond {{1}, {2}, {3}, {4}, {5}} be represented by r. As before, we must calculate µ(r, p) for all bonds p in the lattice. For each bond in the lowest two levels, this process is simple: the finest bond has a value of 1, while each bond in the second level has value -1. To compute the Möbius Function values for bonds in the third and fourth levels, we set up mini-lattices for each bond. For example, if we consider the bond {{1, 4}, {3, 5}, {2}}, we can set up the mini-lattice given in Figure 23, which contains this bond and all finer bonds. Using the Möbius Function, we find that µ(r, {{1, 4}, {3, 5}, {2}}) = 1. It can be calculated that every bond in the third level has a value of 1 under the Möbius Function. Next, we consider a bond on the fourth level, {{1, 2, 3}, {4, 5}}, and set up a mini-lattice for this bond in Figure 24. Again using the Möbius Function, we find that µ(r, {{1, 2, 3}, {4, 5}}) = −1 and that all bonds on this level have a function value of −1. To find the function value for the coarsest bond, {1, 2, 3, 4, 5}, we simply sum together the values for every other bond and then assign this bond the additive THE CHROMATIC POLYNOMIAL 19 Figure 21. A cycle graph with 5 vertices. inverse of this value. Thus, if we sum together all other Möbius Function values, we find that the sum is −4. As a result, µ(r, {1, 2, 3, 4, 5}) = 4. We can now fill out our bond lattice with the Möbius Function value for each bond, as is done in Figure 25. As before, we notice that all bonds that are found on the same level of the lattice have the same number of parts. Thus, for all bonds p that occur on the same level, Na (p) = k i , where i is the common number of parts. Then, we once again sum up the Möbius Function values for all the bonds on a particular level and as the coefficient of k i in our sum. As P use this resulting value 5 a result, Ne (r) = p:r≤p µ(r, p)Na (p) = k − 5k 4 + 10k 3 − 10k 2 + 4k, and we have found the Chromatic Polynomial of the path graph on 5 vertices as desired. We double-check our answer using Theorem 1. The calculations are given in Figure 26. From the diagrams, we see that the Chromatic Polynomial is k(k − 1)4 − [k(k − 1)3 − k(k − 1)(k − 2)] = k 5 − 5k 4 + 10k 3 − 10k 2 + 4k, as desired. 8. Characteristics of the Chromatic Polynomial We now utilize our method of computing Chromatic Polynomials by use of the bond lattices and the Möbius Inversion Theorem to prove characteristics of the Chromatic Polynomial. First, we consider that in the Chromatic Polynomial of a graph of n vertices, the coefficient of the k n−1 term is always the negative of the number of edges in the graph. This is because the second level of any bond lattice is composed of bonds that contain only an edge and singleton vertices. Thus, the number of bonds in the second level of a bond lattice is always the number of edges of the graph. Also, because the first level is always composed of only one bond that always has a Möbius Function value of 1 and is always finer than every bond on the second level, each bond on the second level will have a function value of -1. Because Na (b) = k n−1 for all bonds b on the second level of any lattice, the coefficient on the k n−1 term will always be the negative of the number of edges in the graph. Next, we show why the coefficients in a Chromatic Polynomial always sum to 0. This is because the Möbius Function value for each bond in the bond lattice of a graph is calculated so that the function value for a particular bond and function values of all finer bonds sum to 0. Particularly, the function value for the coarsest bond in the bond lattice is chosen so that the sum of all function values of all bonds in the lattice is 0. Also, we note that plugging k = 1 into any Chromatic Polynomial is the same as summing together all of the coefficients. For any graph with at least one edge, this sum will always be 0 as such a graph cannot be properly colored with k = 1 colors. 20 Figure 22. The bond lattice for the path graph with 5 vertices (Intermediate lines have been removed to avoid confusion). THE CHROMATIC POLYNOMIAL 21 Figure 23. The mini-lattice for the bond {{1, 4}, {3, 5}, {2}}. Figure 24. The mini-lattice for the bond {{1, 2, 3}, {4, 5}}. To explain why the signs on the coefficients of the Chromatic Polynomial alternate, we utilize an induction proof on the bond lattice of a graph. Our base case is a bond lattice that consists of only two levels. The lower level will consist of only the bond in which each vertex is in a separate part; this bond will always have a Möbius Function value of 1. On the second level, any bond b will have a function value of −1 because the bond on the first level will be finer than b and this is in fact that only bond finer than b. Thus, the Chromatic Polynomial for the graph described by this bond lattice will be k i − jk i−1 , where j is the number of bonds 22 Figure 25. The bond lattice for the path graph with all Möbius Function values included. THE CHROMATIC POLYNOMIAL 23 Figure 26. The calculation of the Chromatic Polynomial for the path graph using Theorem 1. on the second level of the lattice. We have thus shown that this Polynomial has alternating coefficients. Now, suppose we have a bond lattice that consists of n levels, where n > 2, and that our result is true for bond lattices of n − 1 levels. If we consider only the first n − 1 levels of our lattice, we know that the Möbius Function values of the bonds on different levels alternate in sign. Now, let b be a bond on the nth level of this lattice. We must show that the Möbius Function value of b is not 0 and that the sign of the function value is different from the signs of the function values for bonds on the n − 1 level. We know b will not have a function value of 0 because we only include bonds in the lattice that correspond to possible subgraphs of the graph we are considering. Now, suppose b is only coarser than one bond on the n − 1 level, denoted by c. This is not possible because the Möbius Function value of b would have to be 0. This would occur because the function value of c is calculated so that the sum of the function values of all bonds finer than c (which, in this case, would be all other bonds finer than b) and the function value for c is 0. Thus, there must be at least 2 bonds on the n − 1 level that are finer than b. Also, the sublattices corresponding to each of these finer bonds must have some sort of overlap, otherwise the function value for b would again be 0. Because of this overlap, when we sum together the Möbius Functon values of all bonds finer than b, we will find that this sum will have the sign of the bonds on the n − 1 level, as these values will dominate in the sum. Thus, the Möbius Function value for b must have an opposite sign in order to get the sum back to 0. As a result, we have shown that the signs of the Möbius Function values in a bond lattice alternate between each level and, consequently, that the coefficients of the Chromatic Polynomial alternate in sign. 24 Figure 27. The graph J, which is made up of the components G and H. The other chracteristic of the Chromatic Polynomial we consider is that the number of components of a graph determines the power of the lowest term in the Chromatic Polynomial. First, we must define connected graphs and components of a graph. A graph is connected if for any two vertices, there is a walk between them. A component of a graph is a maximal connected subgraph. For example, in Figure 27, if J is the graph given, then the graphs G and H are components of J. Now, suppose L is a graph that is composed of only one component. If we construct the bond lattice of this graph, we know that it will have h levels, where h is the number of vertices in the graph. Also, the sum of the Möbius Function values for the bonds of the jth level of the lattice will correspond to the coefficient of the k h+1−j term in the Chromatic Polynomial of L. Because the lattice has h levels, the sum of the Möbius Function values for the highest level, or hth level, will correspond to to the k h+1−h = k 1 term; this will also be the lowest power of k in the Chromatic Polynomial. Now, suppose L has n components. We can determine the Chromatic Polynomial of each component separately and we know the lowest term of k in each will be k 1 . To find the Chromatic Polynomial for L, we multiply the Chromatic Polynomials of all of L’s components together, as any coloring on a particular component will be independent of the colorings on the other components. This produces a new polynomial, for which the lowest term of k is k n . 9. Conclusion We have now shown the connection that exists between Graph Theory and partially ordered sets and this connection has led us to develop a universal method for computing the Chromatic Polynomial of any graph we choose. The cornerstone of this method is the Möbius Inversion Theorem. We have seen that this theorem is a very powerful tool that can be utilized within any combinatorial problem in which objects are assigned properties. Particularly, we need only to construct the bond lattice of a given graph and then apply the Möbius Inversion Theorem to find the Chromatic Polynomial of a given graph. As further study of this topic, we could explore the calculation of Chromatic Polynomials given different restrictions on the colorings of a graph. For example, we could explore colorings for which particular pairs of adjacent vertices are the same color or colorings for which adjacent vertices are not similar colors. Another possible topic could be Chromatic Polynomials for edge colorings. Richard Stanley’s THE CHROMATIC POLYNOMIAL 25