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

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

%d bloggers like this:

The Chromatic Polynomial of South America is

Map:

Proof:

Brasil

Colombia

Venezuela

Guayana

Suriname

Guyana

Perú

Ecuador

Bolivia

Paraguay

Argentina

Uruguay

Chile

have roots at , therefore there is no way of color the map properly with less than 4 colors. In consequence, and the minimum way of performing the task is 6144.

But now, some interesting questions arise.

Suppose kid A have the following preferences (over the set of colors) such that: That means that he’ll use color 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 ?

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

Any thoughts?

Actually, Chile has only colors (not ).

Sorry about that.

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

The Chromatic Polynomial of South America is

**********Case 1: Argentina = Perú (Then )**********

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: **********

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):

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) 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, 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

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 , not , 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 . Substituting and then simplifying gives that the chromatic polynomial for South America is .

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

which doesn’t split over (or even ). 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 , but is the converse also true?

Thanks dgklein.

have roots in , therefore there is no way of color the map properly with less than 4 colors. In consequence, and the minimum ways of performing the task are 9216.

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