Rook Polynomial.

 

1. Definition.

Given a board B of size m-by-n and available squares, its Rook polynomial,

R(B) =  S a_k x^k , k = 0,1,2, …, min(m,n) where  each a_k   represents the number of different ways to position k Rooks to the available squares of the given board.

 

2. Example.

 

B:

		*	*
			*
	*			*
				*

                  where * denotes an available square.

           

For this board, the Rook Polynomial is:

R(B) = 1 + 6x + 11x² + 6x³  + x⁴    

 

3. Reduction Methods.

 

• Empty Row (or Column) deletion

Consider the following board, B’, we get from the above board by deleting the empty first column and the empty fourth row.

     

B’

	*	*
		*
*			*
			*

 

It is easy to see that:  R(B) = R(B’)

    

 

•   Perfect decomposition

 

B

		*	*
			*	*
	*
*	*
*

                       

                        B1

           

	*
*	*
*

 

 

                        B2

 

		*	*
			*	*

 

In this case, R(B) = R(B1)*R(B2)

 

This is the case where the original board, B,  is decomposed into two disjoint non-empty boards B1 and B2 such that 

1.      every available square of B is either in B1 or B2 (and NOT in both)

2.      and each available square of B1 is not in the same row or in the same column as any available square of B2 and vice versa.

Such a perfect decomposition may or may not be possible.

For example, the following board may not be decomposed this way:

 

		*	*
			*	*
	*
	*	*
*		*

 

 

• Single Square Decomposition: Always applicable unless the board is empty.

 

		**	*
			*
	*			*
				*

 

                        Given a board, consider any one available square, s.

                        In this case, w.r.t this available square s, we can get two boards, B1 

                        and  B2 as follows:

 

                        B1: The result of deleting the row and the column of this square s

 

		*
	*		*
			*

 

                        B2: The result of just making this square “Unavailable”

 

			*
			*
	*			*
				*

 

                        Now, R(B) = x*R(B1) + R(B2)

 

• Complementary Reduction

When a board has excessively many available squares, considering its complementary board makes sense.

 

   B                                        C(B) = Complement of B

	*	*	*	*	!	!	*
*	*		*		!	!			*		*
*	*	*	*	*	!	!
*	*		*	*	!	!			*
	*	*	*		!	!	*				*

 

Before we tackle this reduction, we need the Principles of Inclusions and Exclusions.

 

Suppose that we have

1.      a sample of 1000 students.

2.      out of these students, 800 are single, 700 are fulltime students and 400 have high-GPA (3.0 or above?)

 

Now, suppose that we want to find out the number of students who are single and fulltime.

What else do we need before we can get this count?

We need the number of students who are non-single and also non-fulltime.

Suppose that this count is 100, that is out of this sample of 1000 students, 100 are both non-single (perhaps married???) and non-fulltime (perhaps part-time).

So, Count(Single,Fulltime) = 1000 – 200 – 300 + 100 = 600

 

Now what if we want Count(Single,Fulltime,HighGPA)?

Let us assume that a student is either single or non-single, Fulltime or part-time and HighGPA or LowGPA and nothing in between.

 

The Principles of Inclusions and Exclusions say that

Count(Single,Fulltime,HighGPA) =

TotalCount – Count(Non-single) – Count(Part-time) – Count(LowGPA)

                    +  Count(Non-single,Part-time)

                    +  Count(Non-single,LowGPA)

                    +  Count(Part-time,LowGPA)  

         - Count(Non-single,Part-time,LowGPA)

      = 1000 – 200 – 300 – 600  + 100 + 150 + 200 – 50 = 300.

 

• Now, back to the Complementary Reduction.

a.  Let B be of size, m-by-n, m>=n and the board B’ be its complement.

b.  Let P_k  be the property that the column k of B has an unavailable

     square occupied, hence violating the rule in the column k.

c.       P(m,n) = m(m-1)(m-2), …, (m-n+1) is the count of all possible

placements of  n Rooks such that no two Rooks are on the same row of B or on the same column of B, whether occupied squares are available or not.

d.      We note that r_n (B) =

number of different ways to place n Rooks onto available squares of B

= P(m,n) -  S C(P_k)P(m-1,n-1) +   S C(P_j P_k)P(m-2,n-2)    

                 1<=k<=n                      j<>k, 1<=j,k<=n       

   -    S C(P_j  P_k P_l)P(m-3,n-3)  +  … + (-1)ⁿ C(P₁  P₂  P₃ …  P_n)P(m-n,0)

       j<>k<>l, 1<=j,k,l<=n

= P(m,n) -  r₁(B’)P(m-1,n-1) +  r₂ (B’)P(m-2,n-2)    

    -  r₃(B’)P(m-3,n-3)  +  … + (-1)ⁿ  r_n (B’)

 

Note:

1.              When  m>=n, P(m,n) is the count of all possible placements of n Rooks as the board is of size m-by-n with m>=n assuming that all squares of the board are available (or assuming that it does not matter whether a square is available or not).

2.               

*	*	*
*	*	*
*	*	*
*	*	*
*	*	*

 

         For example, P(5,3)=5*4*3=60 placements of 3 Rooks onto above

         board. 

 

                  Permutation               Squares used

 

                  123:                             (1,1), (2,2), (3,3)

                  132:                             (1,1), (3,2), (2,3)

                  523:                             (5,1), (2,2), (3,3)

                  543:                             (5,1), (4,2), (3,3)

    

3.               

*	*	*	*
*	*	*	*
*	*	*	*
*	*	*	*
*	*	*	*

 

         For the above board, the count of all placements of 3 Rooks (instead

         of 4) will be: P(5,3)C(4,3).

         Here, P(5,3) is the count of all placements of 3 Rooks when three columns

         are selected out of four and used throughout as if the board had only three

         columns. And there are C(4,3)=4 ways of selecting 3 columns out of 4

         the board has.

         Generalizing this idea, the count of all placements of j Rooks onto a board

         of size m-by-n, m>=n, is:

                  P(m,j)C(n,j) which is the same as: P(n,j)C(m,j), m>=n>j.

                  P(m,j)C(n,j) = m!/(m-j)! * n!/(j!)(n-j)!)

                                        = m!n! / ((m-j)!j!(n-j)!)

                  P(n,j)C(m,j) = n! / (n-j)! * m!/(j!)(m-j)!)

 

Example:

 

B’

		*	*
			*
	*			*
				*

R(B’) = 1 + 6x + 11 x*x + 6 x*x*x + x*x*x*x

r₅(B)  =  5! – 4!(6) + 3!(11) – 2!(6) + 1!(1) = 31

 

e.       r_j (B) when j<n (namely, when not all n columns are used) 

=  P(m,j)C(n,j) -  S C(P_k)P(m-1,j-1)C(n-1,j-1) +   S C(P_k P_q)P(m-2,j-2)C(n-2,j-2)    

                          1<=k<=n                                     q<>k, 1<=q,k<=n       

 - S C(P_q  P_k P_l)P(m-3,j-3)C(n-3,j-3)+ …+ (-1)^j C(P_q  P_k  P_l …P_s)P(m-j,0)C(n-j,0)

                               q<>k<>l, 1<=q,k,l<=n                                                                         

 

=  P(m,j)C(n,j) -  r₁(B’)P(m-1,j-1)C(n-1,j-1) +  r₂(B’)P(m-2,j-2)C(n-2,j-2)    

   -   r₃(B’)P(m-3,j-3)C(n-3,j-3)  +  … + (-1)^j C(P_q  P_k  P_l …P_s)P(m-j,0)C(n-j,0)

     

Continuing on the same example above, we see that

r₄(B)  =  P(5,4)C(5,4) – P(4,3)C(4,3)*6 + P(3,2)C(3,2)*11 – P(2,1)C(2,1)*6 +

               P(1,0)C(1,0)*1 = 5!5 – 4!*4*6 + 3!*3*11 – 2!*2*6 + 1

                                        =  600 – 576 + 198 – 24 + 1 = 199

r₃(B)  =  P(5,3)C(5,3) – P(4,2)C(4,2)*6 + P(3,1)C(3,1)*11 – P(2,0)C(2,0)*6

          =   5*4*3(5*4/2) – 4*3(4*3/2)*6 + 3*3*11 – 6

          =  600 – 432 + 99 – 6 = 261

r₂(B)  =  P(5,2)C(5,2) – P(4,1)C(4,1)*6 + P(3,0)C(3,0)*11

                                        =   20*10 – 4*4*6 + 11 = 115

                              r₁(B)  =  P(5,1)C(5,1) – P(4,0)C(4,0)*6

                                        =   25 – 6 = 19 (as expected)

 

                              So, completing this example board, we get:

R(B) = 1 + 19x + 115 x²  + 261x³ + 199 x⁴ + 31 x⁵ 

 

                                     

*	*			*
*	*	*		*
*		*	*
*	*	*	*	*
*	*	*	*

 

 

Chromatic Polynomial

 

Definition:

Given an undirected graph G, P(G,x) is a polynomial in x whose value is the number of different ways to color this graph

in x colors so that any two adjacent vertices must have different colors.

 

Example:

 

            K₃   : A complete graph with three nodes.  

            P(K₃ ,x) = x(x-1)(x-2)

 

 

 

 

 

 

            Note

1.  P(K₃ ,x) = 0 if x<=2, that is, it is impossible to color this graph in 2 or fewer

                 colors as we need at least three colors for it.

2.      P(K₃ ,3) = 6  

In this case, there are six different ways to color this graph.

They are:   

GRB, GBR, RBG, RGB, BGR, BRG for the three vertices of the graph.

3.      P(K₄ ,x) = x(x-1)(x-2)(x-3):

where K₄ is a Complete graph with four vertices

 

Fundamental Reduction Theorem:

 

Suppose that we obtain two graphs, G1 and G2, from a given graph G as follows:

    G1:  Result of simply deleting an edge, e, of G and no other change to G. In particular,

            we retain two vertices connected by this edge we delete.

    G2:  Result of not only deleting this edge e but also combining the two incident

            vertices into either one thereby deleting one of them.

 

In this case, we have:  P(G,x) = P(G1,x) – P(G2,x)

 

Example:

 

                                                                             

                                    G:                                          

 

 

 

 

 

 

                                    G1:                                                     G2:                            

 

  

 

 

Note that for the same G and G1 above, G2 may be different depending upon which vertex has been absorbed. But, we will have the same result.

 

Another Example:

 

                a                      b

              

 

 

                c                      d

 

Direct Computation.

 

For the above graph, there are two cases to consider: 

    Case-1: vertex b and vertex c get the same color

    Case-2: they get different colors.

For case-1, we have x(x-1)(x-1): x for vertex a, (x-1) for both vertices b and c, and

                  (x-1) for vertex d alone.

For case-2, we have x(x-1)(x-2)(x-2)

 

                             a       b       d        c

So, P(G,x) = x(x-1)(x-1) + x(x-1)(x-2)(x-2)

                  = x(x-1)(x-1+x²- 4x + 4)

                  =  (x²- x) (x²- 3x + 3)

                  =   x⁴-  4x³ +  6x²- 3x                

 

 

 Using the Fundamental Reduction Theorem.

 

       G1:                                      G2: 

 

 

 

 

 

 

 

 

 

      G1  à          G11:                                    G12:                   

 

 

 

 

 

P(G1,x) = x(x-1)x(x-1) – x(x-1)(x-1)

P(G2,x) = P(K₃ ,x) = x(x-1)(x-2)

So, P(G,x) = (x(x-1)x(x-1) – x(x-1)(x-1) ) -  x(x-1)(x-2)

                  = x(x-1)(x-1)(x-1) – x(x-1)(x-2)

                  = x(x-1)(x ² - 2x +1 – (x-2))

                  = x(x-1)( x ² - 3x + 3)

                  = (x ² - x)( x ² - 3x +3)    

                  = x⁴-  4x³ +  6x²- 3x          :The same result.

 

Some properties of Chromatic Polynomials

 

Suppose that G is a graph of n vertices and

P(G,x) =  a_p x^p  +   a_p-1 x^p-1 + a_p-2 x^p-2  + … + a₀  of degree p.

 

1. p=n, the number of vertices.
2. a_p =  a_n = 1.
3. a₀ = 0 (The constant term)
4. Either P(G,x) =  xⁿ   or the sum of all coefficients is zero.  
5. Absolute value of the coefficient of x^n-1 is the same as the number of edges of G.    
6. The coefficients have alternating signs and
7. If a_k  is zero then  a_k-1  =  a_k-2  =   …  =  a₀  = 0                                 

 

Note that P2(x) =  x⁴  -  4x³  +  3x²   cannot be a Chromatic polynomial for any graph

although it satisfies all properties mentioned above. Why not???                                                                                     

   There are only two graphs with four vertices and four edges.

   They are:

 

            G1:                                         G2:

 

 

 

 

 

Now,  we already have:  P(G1,x) =   x⁴-  4x³ +  6x²- 3x

P(G2,x) = x(x-1)(x-2)x – x(x-1)(x-2)

              = x(x-1)(x-2)(x-1)

              = (x²- x )(x²- 3x  + 2)  =  x⁴-  4x³ +  5x²- 2x

So, above polynomial P2(x) cannot possibly be a Chromatic polynomial of a graph with 4 vertices and 4 edges and hence it is not a Chromatic polynomial.