Chromatic polynomial of South America

As I asked in Lecture 2: What is the number of proper colorings (where no two neighbors have the same color) of the map of South America using at most q given colors? What is the smallest number of colors possible?

Advertisements

8 comments

  1. The Chromatic Polynomial of South America is C(q)=q(q-1) (q-2)^9 (q-3)^2
    Map:

    Proof:
    Brasil q
    Colombia (q-1)
    Venezuela (q-2)
    Guayana (q-2)
    Suriname (q-2)
    Guyana (q-2)
    Perú (q-2)
    Ecuador (q-2)
    Bolivia (q-2)
    Paraguay (q-2)
    Argentina (q-3)
    Uruguay (q-2)
    Chile (q-2)

    C(q) have roots at q=0,1,2,3, therefore there is no way of color the map properly with less than 4 colors. In consequence, \widetilde{q}=4 and the minimum way of performing the task is 6144.

  2. But now, some interesting questions arise.

    Suppose kid A have the following preferences (over the set of colors) such that: q_{1} \succeq q_{2} \succeq ... \succeq q_{n} That means that he’ll use color q_{1} over any other if able (’cause it makes him happier), otherwise he chooses the next one.

    1) Given any startpoint, How many states he could color with q_{1}?

    2) he doesn’t like his paint if less than a half of the state are in q_{1} . What is the probability of kid A to enjoy his painting? (we assume that all start point are equally likely)

    Any thoughts?

  3. Actually, Chile has only (q-3) colors (not (q-2)).
    Sorry about that.

  4. Andrés, you are very close, but the last step has a problem: whether Chile has q-2 or q-3 colors available depends on whether you gave Peru and Argentina different colors. I’m sure you’ll be able to adapt your argument easily.
    Your questions are interesting. In looking for answers, you might want to look into the “chromatic symmetric function”; see for example http://www-math.mit.edu/~rstan/transparencies/3plus1.pdf

  5. \emph{Correction:}
    The Chromatic Polynomial of South America is C(q)=q(q-1) (q-2)^10 (q-3)

    \emph{The Map:}

    \emph{Proof:}
    **********Case 1: Argentina = Perú (Then Paraguay \neq Peru )**********

    Brasil q
    Colombia (q-1)
    Venezuela (q-2)
    Guayana (q-2)
    Suriname (q-2)
    Guyana (q-2)
    Perú (q-2)
    Ecuador (q-2)
    Bolivia (q-2)
    Argentina (1)
    Paraguay (q-3)
    Uruguay (q-2)
    Chile (q-2)

    **********Case 2: Argentina \neq Peru **********

    Sub-case (a): Perú = Paraguay
    Brasil q
    Colombia (q-1)
    Venezuela (q-2)
    Guayana (q-2)
    Suriname (q-2)
    Guyana (q-2)
    Perú (q-2)
    Ecuador (q-2)
    Bolivia (q-2)
    Paraguay (1)
    Argentina (q-3)
    Uruguay (q-2)
    Chile (q-3)

    Sub-case (b): Peru \neq Paraguay
    Brasil q
    Colombia (q-1)
    Venezuela (q-2)
    Guayana (q-2)
    Suriname (q-2)
    Guyana (q-2)
    Perú (q-2)
    Ecuador (q-2)
    Bolivia (q-2)
    Paraguay (q-3)
    Argentina (q-3)
    Uruguay (q-2)
    Chile (q-3)

    Adding each case, we get:
    C(q)=q(q-1) (q-2)^9 (q-3) + q(q-1) (q-2)^8 (q-3)^2 + q(q-1) (q-2)^8 (q-3)^3
    C(q)=q(q-1) (q-2)^8 (q-3)[(q-2)+(q-3)+ (q-3)^2]
    C(q)=q(q-1) (q-2)^8 (q-3)[(q-2)+(q-3)(1 + (q-3))]

    C(q)=q(q-1) (q-2)^10 (q-3)

    C(q) have roots at q=0,1,2,3, therefore there is no way of color the map properly with less than 4 colors. In consequence, \widetilde{q}=4 and the minimum ways of performing the task are 12288.

    Federico: I tried a more direct method but i couldn’t succeed.
    I’ll also check the chromatic symmetric function next week.
    thanks

    • dgklein

      Hmm… I’m not sure I agree with this. There seems to be an issue with the LaTeX in the case descriptions, but I’m guessing that Case 2(b) is where Argentina and Paraguay both have different colors from Perù. I think that in this case, the factor for Argentina should be q - 4, not q - 3, because Argentina must have a different color from each of Brazil, Perù, Bolivia, and Paraguay (all of which must have different colors), so the polynomial for this case is q(q - 1)(q - 2)^8 (q - 3)^2 (q - 4). Substituting and then simplifying gives that the chromatic polynomial for South America is q(q - 1)(q - 2)^8 (q - 3)(q^2 - 5q + 7).

      What got me thinking about this was Federico’s question about finding an ordering where you don’t have to split into cases and add. I don’t think one exists, because if you look at Brazil, Perù, Chile, and Argentina, each of these countries borders two of the others that don’t share a border, so no matter what order you choose for these countries, when you get to the last country, you’ll have colored two countries that border it but don’t border each other, so you could have colored these countries different colors or the same color. Hence, you have to add to cover these different cases, and so I don’t think you can avoid adding, no matter what order you choose.

      This leads to a more general question. If we just look at Brazil, Perù, Chile, and Argentina, the chromatic polynomial for these four countries is
      q(q - 1)(1)(q - 1) + q(q - 1)(q - 2)(q - 2) = q(q - 1)(q^2 - 3q + 3)
      which doesn’t split over \mathbf{Z} (or even \mathbf{R}). It’s clear that if you can produce an ordering in which you don’t have to add, then the chromatic polynomial must split over \mathbf{Z}, but is the converse also true?

  6. If the polynomial factors into linear factors, there probably *should* be an order of the countries that gives this directly. [Edited later:] In this case, it doesn’t.
    By the way, you may be interested in Bruce Sagan’s paper “Why the characteristic polynomial factors”:
    http://www.math.msu.edu/~sagan/Papers/Old/cpf-ams.pdf

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: